

<!DOCTYPE html>
<html lang="zh-CN" data-default-color-scheme=&#34;auto&#34;>



<head>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="/img/insert1.png">
  <link rel="icon" href="/img/insert1.png">
  <meta name="viewport"
        content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  
  <meta name="theme-color" content="#2f4154">
  
    <meta name="description" content="无聊的人生只剩下无尽的空虚。">
  
  <meta name="author" content="Mike Taylor">
  <meta name="keywords" content="我的博客">
  
  <title>操作系统总复习 - Mike Taylor</title>

  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/bootstrap@4.5.3/dist/css/bootstrap.min.css" />


  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/github-markdown-css@4.0.0/github-markdown.min.css" />
  <link  rel="stylesheet" href="/lib/hint/hint.min.css" />

  
    
    
      
      <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/highlight.js@10.4.0/styles/github-gist.min.css" />
    
  

  
    <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.css" />
  



<!-- 主题依赖的图标库，不要自行修改 -->

<link rel="stylesheet" href="//at.alicdn.com/t/font_1749284_ba1fz6golrf.css">



<link rel="stylesheet" href="//at.alicdn.com/t/font_1736178_kmeydafke9r.css">


<link  rel="stylesheet" href="/css/main.css" />

<!-- 自定义样式保持在最底部 -->


  <script id="fluid-configs">
    var Fluid = window.Fluid || {};
    var CONFIG = {"hostname":"gitee.com","root":"/","version":"1.8.8","typing":{"enable":true,"typeSpeed":30,"cursorChar":"|","loop":false},"anchorjs":{"enable":true,"element":"h1,h2,h3,h4,h5,h6","placement":"right","visible":"hover","icon":""},"progressbar":{"enable":true,"height_px":3,"color":"#29d","options":{"showSpinner":false,"trickleSpeed":100}},"copy_btn":true,"image_zoom":{"enable":true},"toc":{"enable":true,"headingSelector":"h1,h2,h3,h4,h5,h6","collapseDepth":0},"lazyload":{"enable":true,"onlypost":false},"web_analytics":{"enable":false,"baidu":null,"google":null,"gtag":null,"tencent":{"sid":null,"cid":null},"woyaola":null,"cnzz":null,"leancloud":{"app_id":null,"app_key":null,"server_url":null}}};
  </script>
  <script  src="/js/utils.js" ></script>
  <script  src="/js/color-schema.js" ></script>
</head>


<body>
  <header style="height: 70vh;">
    <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand"
       href="/">&nbsp;<strong>Mike Taylor's</strong>&nbsp;</a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/">
                <i class="iconfont icon-home-fill"></i>
                主页
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/archives/">
                <i class="iconfont icon-archive-fill"></i>
                日志
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/categories/">
                <i class="iconfont icon-category-fill"></i>
                目录
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/tags/">
                <i class="iconfont icon-tags-fill"></i>
                标签
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/about/">
                <i class="iconfont icon-user-fill"></i>
                个人
              </a>
            </li>
          
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" data-toggle="modal" data-target="#modalSearch">&nbsp;<i
                class="iconfont icon-search"></i>&nbsp;</a>
          </li>
        
        
          <li class="nav-item" id="color-toggle-btn">
            <a class="nav-link" href="javascript:">&nbsp;<i
                class="iconfont icon-dark" id="color-toggle-icon"></i>&nbsp;</a>
          </li>
        
      </ul>
    </div>
  </div>
</nav>

    <div class="banner" id="banner" parallax=true
         style="background: url('/img/default.png') no-repeat center center;
           background-size: cover;">
      <div class="full-bg-img">
        <div class="mask flex-center" style="background-color: rgba(0, 0, 0, 0.3)">
          <div class="page-header text-center fade-in-up">
            <span class="h2" id="subtitle" title="操作系统总复习">
              
            </span>

            
              <div class="mt-3">
  
    <span class="post-meta mr-2">
      <i class="iconfont icon-author" aria-hidden="true"></i>
      Mike Taylor
    </span>
  
  
    <span class="post-meta">
      <i class="iconfont icon-date-fill" aria-hidden="true"></i>
      <time datetime="2021-04-19 10:01" pubdate>
        2021年4月19日 上午
      </time>
    </span>
  
</div>

<div class="mt-1">
  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-chart"></i>
      28.1k 字
    </span>
  

  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-clock-fill"></i>
      
      
      291
       分钟
    </span>
  

  
  
    
      <!-- 不蒜子统计文章PV -->
      <span id="busuanzi_container_page_pv" style="display: none">
        <i class="iconfont icon-eye" aria-hidden="true"></i>
        <span id="busuanzi_value_page_pv"></span> 次
      </span>
    
  
</div>

            
          </div>

          
        </div>
      </div>
    </div>
  </header>

  <main>
    
      

<div class="container-fluid nopadding-x">
  <div class="row nomargin-x">
    <div class="d-none d-lg-block col-lg-2"></div>
    <div class="col-lg-8 nopadding-x-md">
      <div class="container nopadding-x-md" id="board-ctn">
        <div class="py-5" id="board">
          <article class="post-content mx-auto">
            <!-- SEO header -->
            <h1 style="display: none">操作系统总复习</h1>
            
              <p class="note note-info">
                
                  本文最后更新于：2021年7月1日 晚上
                
              </p>
            
            <div class="markdown-body">
              <p>教材：《计算机操作系统》（第四版） 汤子丹等</p>
<h1 id="第三章-处理机调度与死锁"><a href="#第三章-处理机调度与死锁" class="headerlink" title="第三章 处理机调度与死锁"></a>第三章 处理机调度与死锁</h1><p>3.1 处理机调度的层次和调度算法的目标</p>
<p>3.2 作业和作业调度</p>
<p>3.3 进程调度 </p>
<p>3.4 实时调度 </p>
<p>3.5 死锁概述 </p>
<p>3.6 预防死锁</p>
<p>3.7 避免死锁</p>
<p>3.8 死锁的检测与解除 </p>
<h2 id="3-1-处理机调度的层次和调度算法的目标"><a href="#3-1-处理机调度的层次和调度算法的目标" class="headerlink" title="3.1 处理机调度的层次和调度算法的目标"></a>3.1 处理机调度的层次和调度算法的目标</h2><p>分配处理机的任务是由处理机调度程序完成。</p>
<p>处理机调度算法是指根据处理机分配策略所规定的处理机分配算法。</p>
<p>由于处理机是最重要的计算机资源，提高处理机的利用率及改善系统性能（吞吐量、响应时间），在很大程度上取决于处理机调度性能的好坏。</p>
<h3 id="3-1-1-处理机调度层次（三级调度）"><a href="#3-1-1-处理机调度层次（三级调度）" class="headerlink" title="3.1.1 处理机调度层次（三级调度）"></a>3.1.1 处理机调度层次（三级调度）</h3><ul>
<li><p>高级调度（High Level Scheduling）</p>
<ul>
<li><p>又称<strong>作业调度、长程调度</strong>（lon=g-term scheduling），调度对象为<strong>作业</strong>。主要功能是根据某种算法，决定将<strong>外存上处于后备队列</strong>中的哪些作业调入内存。它为被调度作业或用户程序创建进程，分配必要的系统资源，并将新创建的进程插入就绪队列，等待短程调度。</p>
</li>
<li><p>作业基本概念。</p>
<ul>
<li><strong>作业（Job）</strong>是一个比程序更为广泛的概念，它不仅包含了通常的程序和数据，而且还应配有<strong>一份作业说明书</strong>，系统根据该说明书来对程序的运行进行控制。<strong>在批处理系统中，是以作业为基本单位从外存调入内存的。</strong></li>
<li><strong>作业步(Job Step)**。通常，在作业运行期间，每个作业都必须经过若干个相对独立，又相互关联的顺序加工步骤才能得到结果，我们把其中的每一个</strong>加工步骤**称为一个作业步，各作业步之间存在着相互联系，往往是把上一个作业步的输出作为下一个作业步的输入。一个典型的作业可分为：“编译”工作步，“链接”工作步和“运行”工作步。</li>
<li><strong>作业流</strong>。若干个作业进入系统后，被依次存放在<strong>外存</strong>上，这便形成了输入的作业流；在操作系统的控制下，逐个作业进行处理，于是便形成了处理作业流。</li>
<li>每当作业进入系统时，系统便为每个作业建立一个<strong>JCB</strong>，根据作业类型将它插入相应的后备队列中。作业调度程序依据一定的调度算法来调度它们，被调度到的作业将会装入内存。在作业运行期间，系统就按照JCB 中的信息对作业进行控制。当一个作业执行结束进入完成状态时，系统负责回收分配给它的资源，撤消它的作业控制块。</li>
<li><strong>批处理系统中，作业进入系统后，先驻留在磁盘上，组织成批处理队列，称为<em>后备队列</em>。长程调度从该队列中选择一个或多个作业，为之创建进程。</strong></li>
</ul>
</li>
<li><p><strong>高级调度主要用于多道批处理系统，在分时、实时系统中不设置高级调度。</strong>因为为了做到及时响应，用户通过键盘输入的命令或数据等都被<strong>直接送入内存</strong>，因而无需配置上述作业调度机制，但也需有某种接纳控制措施来限制进入系统的用户数目，实时系统类似。</p>
</li>
<li><p><a href="https://imgtu.com/i/cojjTe"><img src="https://z3.ax1x.com/2021/04/19/cojjTe.png" srcset="/img/loading.gif" alt="cojjTe.png"></a></p>
</li>
<li><p>选择多少作业进入内存：<br>作业调度每次要接纳多少个作业进入内存，取决于<strong>多道程序度</strong>(Degree of Multiprogramming)，即<strong>允许多少个作业同时在内存中运行</strong>。当内存中同时运行的作业数目太多时，可能会影响到系统的服务质量，比如，使周转时间太长。但如果在内存中同时运行作业的数量太少时，又会导致系统的资源利用率和系统吞吐量太低，因此，多道程序度的确定应根据系统的规模和运行速度等情况做适当的折衷。</p>
<p>选择哪些作业进入内存：取决于高级调度算法</p>
</li>
</ul>
</li>
<li><p>低级调度(Low Level Scheduling)</p>
<ul>
<li><p>又称<strong>进程调度或短程调度</strong>(Short-term Scheduling)，调度对象是：<strong>进程（内核级线程）</strong>。</p>
</li>
<li><p>低级调度用来决定就绪队列中的哪个进程应获得处理机，然后再由分派程序把处理机分配给该进程的具体操作。</p>
</li>
<li><p>功能：</p>
<ul>
<li>保存处理机的现场信息。在进程调度进行调度时，首先需要保存当前进程的处理机的现场信息，如程序计数器、多个通用寄存器中的内容等，将它们送入该进程的进程控制块(PCB)中的相应单元。</li>
<li>按某种算法选取进程。低级调度程序按某种算法如优先法、轮转法等，从就绪队列中选取一个进程，把它的状态改为运行状态，并准备把处理机分配给它。</li>
<li>把处理器分配给进程。由分派程序(Dispatcher)把处理器分配给进程。此时需为选中的进程恢复处理机现场，即把选中进程的进程控制块内有关处理机现场的信息装入处理器相应的各个寄存器中，把处理器的控制权交给该进程，让它从取出的断点处开始继续运行。</li>
</ul>
</li>
<li><p>进程调度是<strong>最基本</strong>的一种调度，<strong>在多道批处理、分时和实时三种OS中，都必须配置。</strong></p>
</li>
<li><p>短程调度运行频率最高。</p>
</li>
<li><p>低级调度分类：</p>
<ul>
<li><p>非抢占方式</p>
<ul>
<li><p>在采用这种调度方式时，一旦把处理机分配给某进程后，便让该进程一直执行，直至该进程完成或发生某事件而被阻塞时，才再把处理机分配给其他进程，<strong>决不允许某进程抢占已经分配出去的处理机</strong>。</p>
</li>
<li><p>引起进程调度：</p>
<p>①正在执行的进程执行完毕，或因发生某事件而不能再继续执行；</p>
<p> ②执行中的进程因提出I／O请求而暂停执行；</p>
<p> ③在进程通信或同步过程中执行了某种原语操作，如P操作（wait操作）、Block原语、 Wakeup原语等。</p>
</li>
<li><p>优点：实现简单，系统开销小，适合批处理任务。</p>
</li>
<li><p>缺点：难以满足实时任务。（硬实时任务）</p>
</li>
</ul>
</li>
<li><p>抢占方式</p>
<ul>
<li>这种调度方式，允许调度程序根据某种原则，去暂停某个正在执行的进程，将已分配给该进程的<strong>处理机重新分配</strong>给另一进程。</li>
<li>原则：<ul>
<li><strong>优先权原则</strong>：通常是对一些重要的和紧急的作业赋予较高的优先权。当这种作业到达时，如果其优先权比正在执行进程的优先权高，便停止正在执行(当前)的进程，将处理机分配给优先权高的新到的进程，使之执行；或者说，允许优先权高的新到进程抢占当前进程的处理机。</li>
<li><strong>短作业优先原则</strong>：当新到达的作业(进程)比正在执行的作业(进程)（<strong>尚需运行时间</strong>）明显的短时，将暂停当前长作业(进程)的执行，将处理机分配给新到的短作业(进程)，使之优先执行；或者说，短作业(进程)可以抢占当前较长作业(进程)的处理机。</li>
<li><strong>时间片原则</strong>：各进程按时间片轮流运行，当一个时间片用完后，便停止该进程的执行而重新进行调度。这种原则适用于分时系统、大多数的实时系统，以及要求较高的批处理系统。</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
<li><p>中级调度(Medium-term scheduling)</p>
<ul>
<li><p>又称<strong>中程调度、内存调度</strong>，引入中级调度的主要目的是为了提高内存利用率和系统吞吐量。 </p>
</li>
<li><p>当内存空间非常紧张时，或处理机找不到一个可执行的就绪进程时，需要选择一个进程（阻塞或就绪状态）<strong>换出到外存</strong>，释放出内存空间给别的进程使用；当内存空间较充裕时，从外存选择一个挂起状态的进程调度到内存（<strong>换入</strong>）。</p>
</li>
<li><p>中级调度决定把外存上的哪些具备运行条件的就绪进程<strong>，重新调入内存</strong>，并修改其状态为就绪状态，挂在就绪队列上等待调度。</p>
</li>
<li><p>实际上是<strong>存储器管理的对换功能</strong>。</p>
</li>
<li><p>补充：可用于作业调度</p>
<p><strong>下面的图很重要！！！</strong></p>
</li>
<li><p><a href="https://imgtu.com/i/cT99qx"><img src="https://z3.ax1x.com/2021/04/19/cT99qx.png" srcset="/img/loading.gif" alt="cT99qx.png"></a></p>
</li>
</ul>
</li>
</ul>
<h3 id="3-1-2-处理机调度算法的目标和准则"><a href="#3-1-2-处理机调度算法的目标和准则" class="headerlink" title="3.1.2 处理机调度算法的目标和准则"></a>3.1.2 处理机调度算法的目标和准则</h3><p>引言：在一个操作系统的设计中，应如何选择调度方式和算法，<strong>在很大程度上取决于操作系统的类型及其目标</strong>。例如，在批处理系统、分时系统和实时系统中，通常都采用不同的调度方式和算法。选择调度方式和算法的准则，有的是面向用户的，有的是面向系统的。</p>
<ul>
<li><p>处理机调度算法的共同目标</p>
<ul>
<li><p>资源利用率。为提高系统的资源利用率，应使系统中的处理机和其他所有资源都尽可能地保持忙碌。</p>
<ul>
<li><p><strong>计算CPU利用率</strong>：</p>
<p><strong>CPU利用率 = CPU有效工作时间/（CPU有效工作时间+CPU空闲等待时间）</strong></p>
</li>
</ul>
</li>
<li><p>公平性。应使诸进程都获得合理的CPU时间，<strong>不会发生饥饿时间</strong>。公平是相对的，对于相同类型的进程应获得相同的服务；但对于不同类型的进程，由于其紧急程度/重要性不同，则应提供不同的服务。</p>
</li>
<li><p>平衡性。由于在系统中可能具有多种类型的进程，为了使系统中的CPU和各种外部设备都能经常处于忙碌状态，调度算法应尽可能保持系统资源使用的平衡性。</p>
</li>
<li><p>策略强制执行。对所制订的策略其中包括安全策略，只要需要，就必须予以准确地执行，即使会造成某些工作的延迟。</p>
</li>
</ul>
</li>
<li><p>批处理系统的目标：</p>
<ul>
<li><p>平均周转时间短。</p>
<ul>
<li><p><strong>所谓周转时间，是指作业从被提交给系统开始，到作业完成为止的这段时间间隔（作业周转时间）</strong></p>
</li>
<li><p><strong>周转时间T包括四部分：</strong></p>
<ul>
<li><strong>作业在外存后备队列上的等待时间</strong></li>
<li><strong>进程在就绪队列上等待进程调度的时间</strong></li>
<li><strong>进程在CPU上执行的时间</strong></li>
<li><strong>进程等待I/O操作的时间</strong></li>
</ul>
<p>后三项在一个作业处理过程中可能发生多次。</p>
</li>
<li><p><strong>平均周转时间</strong>：</p>
<p><a href="https://imgtu.com/i/cTFiXd"><img src="https://z3.ax1x.com/2021/04/19/cTFiXd.png" srcset="/img/loading.gif" alt="cTFiXd.png"></a></p>
<p>从系统管理者角度出发，平均周转时间越短越好。</p>
</li>
<li><p><strong>带权周转时间：作业的周转时间T</strong> <strong>/</strong> <strong>系统为其提供服务的时间T<sub>s</sub></strong></p>
<p><strong>W = T/T<sub>s</sub></strong></p>
<p><a href="https://imgtu.com/i/cTFP6H"><img src="https://z3.ax1x.com/2021/04/19/cTFP6H.png" srcset="/img/loading.gif" alt="cTFP6H.png"></a></p>
</li>
</ul>
</li>
<li><p>系统吞吐量高。</p>
<ul>
<li><strong>吞吐量：单位时间内系统所完成的作业数</strong>，与处理作业的平均长度有关。</li>
<li>单纯为了提高吞吐量，就应尽量选择短作业处理。</li>
</ul>
</li>
<li><p>处理机利用率高。</p>
<ul>
<li>处理机利用率：衡量系统性能的重要指标。</li>
<li>单纯为了提高处理机利用率，应尽量选择计算量大的作业进行处理。</li>
</ul>
</li>
</ul>
</li>
<li><p>分时系统的目标</p>
<ul>
<li>响应时间快。<ul>
<li><strong>响应时间：是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间。</strong></li>
<li>响应时间包括三部分：<ul>
<li><strong>从键盘输入的请求信息传送到处理机的时间</strong></li>
<li><strong>处理机对请求信息进行处理的时间</strong></li>
<li><strong>将所形成的响应信息回送到终端显示器的时间</strong></li>
</ul>
</li>
</ul>
</li>
<li>均衡性。指系统响应时间快慢应与用户请求的复杂性相适应。</li>
</ul>
</li>
<li><p>实时系统的目标</p>
<ul>
<li>截止时间保证。<ul>
<li><strong>截止时间：指某任务必须开始执行的最迟时间，或必须完成的最迟时间。</strong></li>
<li>可预测性。</li>
</ul>
</li>
</ul>
</li>
</ul>
<h2 id="3-2-作业和作业调度"><a href="#3-2-作业和作业调度" class="headerlink" title="3.2 作业和作业调度"></a>3.2 作业和作业调度</h2><p>多道批处理系统：</p>
<ul>
<li>用户提交作业</li>
<li>操作员输入作业，存放在外存，作业存放在后备队列</li>
<li>由作业调度（长程调度）程序调入内存</li>
</ul>
<h3 id="3-2-1-批处理系统中的作业"><a href="#3-2-1-批处理系统中的作业" class="headerlink" title="3.2.1 批处理系统中的作业"></a>3.2.1 批处理系统中的作业</h3><p>1.作业和作业步（上面已详细说明）</p>
<p>2.作业控制块（Job Control Block，JCB）</p>
<p>JCB包含：作业标识、用户名称、用户账号、作业类型（CPU繁忙型、I/O繁忙型、批量型、终端型）、作业状态、调度信息、资源需求、资源使用情况等。</p>
<p>每当一个作业进入系统时，便由“作业注册”程序为该作业建立一个作业控制块JCB，再根据作业类型，将它放到相应的作业后备队列中，等待调度。调度程序按一定的调度算法来调度它们，被调度的作业将被装入内存。作业运行期间，系统按照JCB中的信息和作业说明书对作业进行控制。当一个作业执行结束进入完成状态，系统负责回收以已分配给它的资源，撤销该作业控制块。</p>
<p>3.作业运行的三个阶段和三种状态<br>作业进入系统到运行结束，通常需要经历：<strong>收容、运行、完成</strong>，三个阶段。相应的作业有<strong>“后备状态”、“运行状态”、“完成状态”</strong>。</p>
<ul>
<li>收容。操作员把用户提交的作业通过某种方式或SPOOLing系统输入到硬盘上，再为该作业建立JCB并把它放入到后备队列中。相应地，此时地作业的状态为“后备状态”。</li>
<li>运行。当作业被调度选中后，便为`它分配必要的资源和建立进程，并将它放入就绪队列。<strong>一个作业第一次进入就绪状态，直到它运行结束前，在此期间处于“运行状态”。</strong></li>
<li>完成阶段。当作业完后、或发生异常情况而提前结束时，作业便进入完成阶段，相应的作业状态为“完成状态”。此时系统中的“终止作业”程序将会回收已经分配给该作业的作业控制块和所有资源，并将作业运行结果信息形成输出文件后输出。</li>
</ul>
<h3 id="3-2-2-作业调度的主要任务"><a href="#3-2-2-作业调度的主要任务" class="headerlink" title="3.2.2  作业调度的主要任务"></a>3.2.2  作业调度的主要任务</h3><p><strong>作业调度</strong>（外存到内存）需要做出以下决定：</p>
<ul>
<li>接纳多少作业（多道程序度）</li>
<li>接纳哪些作业（调度算法）</li>
</ul>
<p>3.2.3 FCFS和SJF算法</p>
<h4 id="先来先服务调度算法"><a href="#先来先服务调度算法" class="headerlink" title="先来先服务调度算法"></a>先来先服务调度算法</h4><p><strong>可用于作业调度，也可以用于进程调度</strong>。</p>
<ul>
<li><p>当在作业调度中采用该算法时，系统安照作业到到达的先后次序来进行调度。优先考虑在系统中等待时间最长的作业，将他们调入内存、分配资源、创建进程，然后放入就绪队列中。</p>
<p>如果在进程调度中采用FCFS，每次调度从就绪队列中挑选最先到达的进程分配处理机。</p>
</li>
<li><p>FCFS很少作为主调度算法，经常与其他调度算法结合使用，形成一种更为有效的调度算法。</p>
</li>
<li><p>FCFS算法比较<strong>有利于长作业（进程）</strong>，而不利于短作业（进程）。</p>
</li>
</ul>
<p><a href="https://imgtu.com/i/cTUVQe"><img src="https://z3.ax1x.com/2021/04/19/cTUVQe.jpg" srcset="/img/loading.gif" alt="cTUVQe.jpg"></a></p>
<h4 id="短作业优先调度算法（SJF）"><a href="#短作业优先调度算法（SJF）" class="headerlink" title="短作业优先调度算法（SJF）"></a>短作业优先调度算法（SJF）</h4><ul>
<li>短作业(进程)优先调度算法<strong>SJ(P)F</strong>，是指对短作业或短进程优先调度的算法。<ul>
<li>短作业优先(SJF)的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们<strong>调入内存</strong>运行。</li>
<li>短进程优先(SPF)调度算法是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，<strong>使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度</strong>。</li>
<li><a href="https://imgtu.com/i/cTarNt"><img src="https://z3.ax1x.com/2021/04/19/cTarNt.jpg" srcset="/img/loading.gif" alt="cTarNt.jpg"></a></li>
</ul>
</li>
<li>短作业优先调度算法的缺点：<ul>
<li>该算法对长作业不利。</li>
<li>该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业（进程）会被及时处理。</li>
<li>由于作业（进程）的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会估计不准运行时间，致使该算法不一定能真正做到短作业优先调度。</li>
</ul>
</li>
</ul>
<h3 id="3-2-4-优先级调度算法和高响应比优先调度算法"><a href="#3-2-4-优先级调度算法和高响应比优先调度算法" class="headerlink" title="3.2.4 优先级调度算法和高响应比优先调度算法"></a>3.2.4 优先级调度算法和高响应比优先调度算法</h3><h4 id="优先级调度算法-priority-scheduling-algorithm-PSA"><a href="#优先级调度算法-priority-scheduling-algorithm-PSA" class="headerlink" title="优先级调度算法(priority-scheduling algorithm,PSA)"></a>优先级调度算法(priority-scheduling algorithm,PSA)</h4><ul>
<li>实际应用中，作业的性质可能是不同，运行的迫切性也有所不同。因此，可以为每个作业定义一个优先级，优先级越高的作业将优先获得调度从后备队列进入内存就绪队列之中。<ul>
<li>当应用于作业调度时，优先级调度算法是把具有最高优先级的作业调入内存之中。</li>
<li>当应用于进程调度时，优先级调度算法是调度就绪队列中具有最高优先级的进程获得处理机。</li>
</ul>
</li>
</ul>
<h4 id="高响应比优先调度算法-Highest-Response-Ratio-Next-HRRN"><a href="#高响应比优先调度算法-Highest-Response-Ratio-Next-HRRN" class="headerlink" title="高响应比优先调度算法(Highest Response Ratio Next,HRRN)"></a>高响应比优先调度算法(Highest Response Ratio Next,HRRN)</h4><ul>
<li><p><strong>引入动态优先级，随等待时间延长而增加。</strong></p>
<ul>
<li><p>响应比R<sub>p</sub> = （等待时间+要求服务时间）/要求服务时间 </p>
<p>​                = 1 + 等待时间/要求服务时间 </p>
<p>​                = 响应时间/要求服务时间</p>
</li>
<li><p>如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。<br>当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。<br>对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而也可获得处理机。简言之，<strong>该算法既照顾了短作业，又考虑了作业到达的先后次序，不会使长作业长期得不到服务</strong>。因此，该算法实现了一种较好的折衷。当然，在利用该算法时，每要进行调度之前，都须先做响应比的计算，这会<strong>增加系统开销</strong>。</p>
</li>
</ul>
</li>
</ul>
<h2 id="3-3-进程调度"><a href="#3-3-进程调度" class="headerlink" title="3.3 进程调度"></a>3.3 进程调度</h2><ul>
<li><p>进程调度的任务：</p>
<ul>
<li>保存处理机现场</li>
<li>按照某种算法选取进程</li>
<li>把处理机分配给进程</li>
</ul>
</li>
<li><p>进程调度机制</p>
<ul>
<li><p>排队器。为提高进程调度的效率，应事先将系统中的所有就绪进程按照一定策略排成一个或多个队列，以便调度程序能最快找到它。以后每当有一个进程变为就绪状态时，排队器就将它插入到相应的就绪队列。</p>
</li>
<li><p>分派器。分派器依据进程调度程序所选的进程，将其从就绪队列中取出，然后进行从分派器到新选出进程间的上下文切换，将处理机分配给新选出的进程。</p>
</li>
<li><p>上下文切换器。在对处理机进行切换时，会发生两对上下文切换操作。</p>
<ul>
<li>第一对上下文切换时，OS将保存当前进程的上下文，即把当前进程的处理机寄存器内容保存到该进程的PCB的相应单元，再装入分派程序的上下文，以便分派程序运行。</li>
<li>第二对上下文切换是移出分派程序的上下文，而把新选进程的CPU现场信息装入到处理机各个相应的寄存器中，以便新进程运行。</li>
<li>进行上下文切换时，需要执行大量的load和store等操作指令，以保存寄存器的内容。</li>
</ul>
<p><a href="https://imgtu.com/i/cTwrSf"><img src="https://z3.ax1x.com/2021/04/19/cTwrSf.png" srcset="/img/loading.gif" alt="cTwrSf.png"></a></p>
</li>
</ul>
</li>
</ul>
<h4 id="进程调度方式"><a href="#进程调度方式" class="headerlink" title="进程调度方式"></a>进程调度方式</h4><p><strong>1.非抢占方式(Nonpreemptive Mode)</strong><br>在这种方式下，系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。<br>不能用于分时系统和实时系统。</p>
<p><strong>2.抢占方式(Preeptive Mode)</strong><br>在这种方式下，系统同样是把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程的执行，重新将处理机分配给新到的优先权最高的进程。<br>抢占的原则：<strong>优先权原则、短进程优先原则、时间片原则</strong></p>
<h3 id="3-3-2-轮转调度算法-Round-Robin-RR"><a href="#3-3-2-轮转调度算法-Round-Robin-RR" class="headerlink" title="3.3.2 轮转调度算法(Round Robin,RR)"></a>3.3.2 轮转调度算法(Round Robin,RR)</h3><ul>
<li><p>在时间片轮转法中，系统将所有的就绪进程<strong>按先来先服务FCFS的原则</strong>，排成一个队列，每次调度时，把CPU分配给队首进程。并令其执行一个时间片。</p>
</li>
<li><p>当执行的时间片用完时，由一个计时器发出时钟<strong>中断请求</strong>，调度程序便据此信号来停止该进程的执行，若程序尚未运行完毕，将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程（或新到达的紧迫进程），同时也让它执行一个时间片。</p>
</li>
<li><p>这样就可以保证就绪队列中的所有进程，在一给定的时间内，均能获得一时间片的处理机执行时间，换言之，系统能在给定的时间内，响应所有用户的请求。</p>
</li>
<li><p>进程切换时机：</p>
<ul>
<li>若一个时间片尚未用完，正在运行的进程便已经完成，就立即激活调度程序，将它从就绪队列删除，再调度就绪队列中队首进程运行，并启动一个新的时间片。</li>
<li>在一个时间片用完时，计时器中断处理程序被激活。如果进程尚未运行完毕，调度程序将它送往就绪队列的末尾。</li>
</ul>
</li>
<li><p>进程切换将会增加系统的额外开销。</p>
<p>时间片设定得太短，进程切换会非常频繁，从而降低处理机的效率；时间片设定得太长，将无法满足交互式用户对响应时间的要求。</p>
<p>因此，时间片大小的确定应综合考虑系统的最大用户数、响应时间、系统效率等多种因素。 </p>
<ul>
<li>例题：</li>
</ul>
<p><a href="https://imgtu.com/i/cHMcXq"><img src="https://z3.ax1x.com/2021/04/20/cHMcXq.jpg" srcset="/img/loading.gif" alt="cHMcXq.jpg"></a></p>
<p><strong>上图有错！！！</strong></p>
<p>为了简单，图中忽略了进程切换时的系统开销，而实际操作系统中，这类额外开销是客观存在的。</p>
<p>采用基于时间片轮转调度法，进程的周转时间和平均周转时间并不比采用FCFS和短进程优先调度算法小。</p>
<p>加上进程切换所需的系统开销时间，该算法的平均周转时间还会增长。</p>
</li>
<li><p>常用于<strong>分时系统及事务处理系统</strong>，合理的时间片大小将带来满意的响应时间。</p>
<p>通常，合理的时间片指，能让**80%**左右的进程在一个时间片内完成。</p>
<p>对于短的、计算型的进程较有利。</p>
<p>不适合于批处理系统的进程调度。</p>
<p>不利于I/O型的进程。</p>
<p>改进的方法之一，可以将I/O阻塞事件完成的进程单独组织一个就绪队列，该队列进程的时间片可以设置的小一些，且优先调度</p>
</li>
<li><p>短作业优先算法平均周转时间最小</p>
</li>
</ul>
<h3 id="3-3-3-优先级调度算法"><a href="#3-3-3-优先级调度算法" class="headerlink" title="3.3.3 优先级调度算法"></a>3.3.3 优先级调度算法</h3><h4 id="优先调度算法类型"><a href="#优先调度算法类型" class="headerlink" title="优先调度算法类型"></a>优先调度算法类型</h4><p>非抢占式优先级调度算法<br>抢占式优先级调度算法</p>
<h4 id="优先级的类型"><a href="#优先级的类型" class="headerlink" title="优先级的类型"></a>优先级的类型</h4><p>优先级调度算法的关键：应该如何确定进程的优先级。</p>
<ul>
<li>静态优先级<ul>
<li>静态优先级是在创建进程时确定的，在进程整个运行期间保持不变。</li>
<li>优先级利用某一范围内的一个整数表示，例如0~255中的某一个整数，把该整数称为<strong>优先数</strong>。</li>
<li>确定进程优先级的依据：<ul>
<li>进程类型。系统进程的优先权高于一般用户进程的优先权。</li>
<li>进程对资源的需求。对要求少的进程应赋予较高的优先权。</li>
<li>用户要求。根据进程的紧迫程度以及用户所付费用的多少确定优先级。</li>
</ul>
</li>
</ul>
</li>
<li>动态优先级<ul>
<li>动态优先级：  动态优先级是指，在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。  <ul>
<li>例如，可以规定<strong>在就绪队列中的进程随其等待时间增长，使其优先级相应提升</strong>。若所有进程具有相同的优先级初始值，则最先进入就绪队列的进程会因其优先级变得最高，而优先获得处理机，这相当于FCFS算法。若所有的就绪进程具有各自不同的优先级初值，那么对于优先级初值低的进程，在等待了足够时间后，也可以得到处理机。<strong>当采用抢占式调度方式时，若再规定当前进程的优先级随时间的推移而下降，则可以防止一个长作业长期地垄断处理机。</strong></li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 id="3-3-4-多队列调度算法"><a href="#3-3-4-多队列调度算法" class="headerlink" title="3.3.4 多队列调度算法"></a>3.3.4 多队列调度算法</h3><ul>
<li><p>将进程的就绪队列拆分为多个</p>
<p>不同类型或性质的进程固定分配在对应的就绪队列</p>
<p>不同的就绪队列采用不同的调度算法</p>
<p>进程可以有不同的优先级、队列也可以有不同的优先级</p>
<p>一个就绪队列中的进程可以设置不同的优先级，不同的就绪队列本身也可以设置不同的优先级。</p>
</li>
</ul>
<h3 id="3-3-5-多级反馈队列调度算法-multileved-feedback-queue"><a href="#3-3-5-多级反馈队列调度算法-multileved-feedback-queue" class="headerlink" title="3.3.5 多级反馈队列调度算法(multileved feedback queue)"></a>3.3.5 多级反馈队列调度算法(multileved feedback queue)</h3><p>应设置多个就绪队列，并为各个队列赋予不同的优先级。 第一个最高，以后依次降低。</p>
<p><a href="https://imgtu.com/i/cHR9Re"><img src="https://z3.ax1x.com/2021/04/20/cHR9Re.png" srcset="/img/loading.gif" alt="cHR9Re.png"></a></p>
<ul>
<li><p>当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。</p>
<ul>
<li>①当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；</li>
<li>②如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；</li>
<li>③如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……。</li>
</ul>
<p>仅当第一队列空闲时，调度程序才调度第二队列中的进程运行。</p>
</li>
<li><p>多级反馈队列调度算法具有较好的性能，能较好地满足各种类型用户的需要。</p>
<ul>
<li>终端型用户。由终端型用户提交的作业多属于交互型作业，通常较小，系统要使作业能在第一队列所规定的时间片内完成，可使终端型作业用户都感到满意。</li>
<li>短批处理作业用户。<strong>对该用户更有利</strong>，周转时间较短。</li>
<li>长批处理作业用户。对于长作业，它将依次在第1，2,…，n个队列中运行，然后再按轮转方式运行，用户不必担心其作业长期得不到处理。</li>
</ul>
</li>
</ul>
<h4 id="小结"><a href="#小结" class="headerlink" title="小结"></a>小结</h4><ul>
<li>如何选择进程调度算法与系统设计的目标有关。</li>
<li>交互式多任务系统，主要考虑联机用户对响应时间的要求，一般采用基于时间片轮转调度算法，同时，根据进程的性质设置不同的优先级。</li>
<li>批处理系统往往以进程（或作业）的平均周转时间来衡量调度性能，常选用基于优先级的短进程（或作业）优先调度算法。 </li>
</ul>
<h2 id="3-4-实时调度"><a href="#3-4-实时调度" class="headerlink" title="3.4 实时调度"></a>3.4 实时调度</h2><p>由于在实时系统中都存在着若干个实时进程或任务，它们用来反应或控制某个外部事件，往往带有某种程度的紧迫性，因而对实时系统中的调度提出了某些特殊要求，前面所介绍的多种调度算法，并不能很好地满足实时系统对调度的要求，为此，需要引入一种新的调度，即<strong>实时调度</strong>。</p>
<h3 id="3-4-1-实现实时调度的基本条件"><a href="#3-4-1-实现实时调度的基本条件" class="headerlink" title="3.4.1 实现实时调度的基本条件"></a>3.4.1 实现实时调度的基本条件</h3><h4 id="提供必要的信息"><a href="#提供必要的信息" class="headerlink" title="提供必要的信息"></a>提供必要的信息</h4><ul>
<li><p><strong>就绪时间</strong>。这是该任务成为就绪状态的起始时间，在周期任务的情况下，它就是事先预知的一串时间序列；而在非周期任务的情况下，它也可能是预知的。</p>
</li>
<li><p><strong>开始截止时间和完成截止时间</strong>。对于典型的实时应用，只须知道开始截止时间，或者知道完成截止时间。</p>
</li>
<li><p><strong>处理时间</strong>。这是指一个任务从开始执行直至完成所需的时间。在某些情况下，该时间也是系统提供的。</p>
</li>
<li><p><strong>资源要求</strong>。这是指任务执行时所需的一组资源。</p>
</li>
<li><p><strong>优先级</strong>。如果某任务的开始截止时间已经错过，就会引起故障，则应为该任务赋予“绝对”优先级；如果开始截止时间的推迟对任务的继续运行无重大影响，则可为该任务赋予“相对”优先级，供调度程序参考。</p>
</li>
</ul>
<h4 id="系统处理能力强"><a href="#系统处理能力强" class="headerlink" title="系统处理能力强"></a>系统处理能力强</h4><p>在实时系统中，通常都有着多个实时任务。若处理机的处理能力不够强，则有可能因处理机忙不过来而使某些实时任务不能得到及时处理。</p>
<p>解决方法：</p>
<ul>
<li>仍是采用单处理机系统，但须增强其处理能力，以显著地减少对每一个任务的处理时间。</li>
<li>采用多处理机系统。</li>
</ul>
<h4 id="采用抢占式调度机制"><a href="#采用抢占式调度机制" class="headerlink" title="采用抢占式调度机制"></a>采用抢占式调度机制</h4><p>在含有硬实时任务的实时系统中，广泛采用抢占机制。当一个优先权更高的任务到达时，允许将当前任务暂时挂起，而令高优先权任务立即投入运行，这样便可满足该硬实时任务对截止时间的要求。</p>
<h4 id="具有快速切换机制"><a href="#具有快速切换机制" class="headerlink" title="具有快速切换机制"></a>具有快速切换机制</h4><p>为保证要求较高的硬实时任务能及时运行，在实时系统中还应具有快速切换机制，以保证能进行任务的快速切换。该机制应具有如下两方面的能力：</p>
<ul>
<li><strong>对外部中断的快速响应能力。</strong>为使在紧迫的外部事件请求中断时系统能及时响应，要求系统具有快速硬件中断机构，还应使禁止中断的时间间隔尽量短，以免耽误时机(其它紧迫任务)。</li>
<li><strong>快速的任务分派能力。</strong>在完成任务调度后，便应进行任务切换。为了提高分派程序进行任务切换时的速度，应使系统中的每个运行功能单位适当地小，以减少任务切换的时间开销。</li>
</ul>
<h3 id="3-4-2-实时调度算法分类"><a href="#3-4-2-实时调度算法分类" class="headerlink" title="3.4.2 实时调度算法分类"></a>3.4.2 实时调度算法分类</h3><p>根据实时任务性质，可将实时调度算法分为：</p>
<ul>
<li>硬实时调度算法</li>
<li>软实时调度算法</li>
</ul>
<p>根据调度方式分类：</p>
<ul>
<li>抢占式调度算法</li>
<li>非抢占式调度算法</li>
</ul>
<h4 id="非抢占式调度算法"><a href="#非抢占式调度算法" class="headerlink" title="非抢占式调度算法"></a>非抢占式调度算法</h4><ul>
<li><p><strong>非抢占式轮转调度算法</strong></p>
<p>调度程序每次选择队列中的第一个任务投入运行。当该任务完成后，便把它挂在轮转队列的末尾，等待下次调度运行。该算法可获得数秒到数十秒的响应时间，可用于要求不太严格的实时控制系统。<br><a href="https://imgtu.com/i/cHfcxe"><img src="https://z3.ax1x.com/2021/04/20/cHfcxe.png" srcset="/img/loading.gif" alt="cHfcxe.png"></a></p>
</li>
<li><p><strong>非抢占式优先调度算法</strong></p>
<p>如果在系统中存在着实时要求较为严格的任务，则可采用非抢占式优先调度算法，为这些任务赋予较高的优先级。当这些实时任务到达时，把它们安排在就绪队列的队首，等待当前任务自我终止或运行完成后，才能被调度执行。</p>
<p><a href="https://imgtu.com/i/cHf2KH"><img src="https://z3.ax1x.com/2021/04/20/cHf2KH.png" srcset="/img/loading.gif" alt="cHf2KH.png"></a></p>
</li>
</ul>
<h4 id="抢占式调度算法"><a href="#抢占式调度算法" class="headerlink" title="抢占式调度算法"></a>抢占式调度算法</h4><ul>
<li><p><strong>基于时钟中断的抢占式优先权调度算法</strong></p>
<p>某实时任务到达后，如果该任务的优先级高于当前任务的优先级，这时并不立即抢占当前任务的处理机，而是等到时钟中断到来时，调度程序才剥夺当前任务的执行，将处理机分配给新到的高优先权任务。 </p>
<p><a href="https://imgtu.com/i/cHfy8O"><img src="https://z3.ax1x.com/2021/04/20/cHfy8O.png" srcset="/img/loading.gif" alt="cHfy8O.png"></a></p>
</li>
<li><p><strong>立即抢占的优先权调度算法</strong></p>
<p>一旦出现外部中断，只要当前任务未处于临界区，便能立即剥夺当前任务的执行，把处理机分配给请求中断的紧迫任务。 </p>
<p><a href="https://imgtu.com/i/cHfsPK"><img src="https://z3.ax1x.com/2021/04/20/cHfsPK.png" srcset="/img/loading.gif" alt="cHfsPK.png"></a></p>
</li>
</ul>
<h3 id="3-4-3-常用的几种实时调度算法"><a href="#3-4-3-常用的几种实时调度算法" class="headerlink" title="3.4.3 常用的几种实时调度算法"></a>3.4.3 常用的几种实时调度算法</h3><h4 id="最早截止时间优先-Earliest-Deadline-First-EDF"><a href="#最早截止时间优先-Earliest-Deadline-First-EDF" class="headerlink" title="最早截止时间优先(Earliest Deadline First)EDF"></a>最早截止时间优先(Earliest Deadline First)EDF</h4><p>该算法要求在系统中保持一个实时任务就绪队列，该队列按各任务截止时间的早晚排序；具有最早截止时间的任务排在队列的最前面。调度程序总是选择就绪队列中的第一个任务，为之分配处理机，使之投入运行。 </p>
<ul>
<li><p>EDF算法用于非抢占式调度方式</p>
<p>四个非周期任务，现后达到</p>
<p><a href="https://imgtu.com/i/cHhlsH"><img src="https://z3.ax1x.com/2021/04/21/cHhlsH.png" srcset="/img/loading.gif" alt="cHhlsH.png"></a></p>
</li>
<li><p>抢占式调度方式用于周期实时任务</p>
<p><a href="https://imgtu.com/i/cH4X40"><img src="https://z3.ax1x.com/2021/04/21/cH4X40.jpg" srcset="/img/loading.gif" alt="cH4X40.jpg"></a></p>
<p><a href="https://imgtu.com/i/cH4vCV"><img src="https://z3.ax1x.com/2021/04/21/cH4vCV.png" srcset="/img/loading.gif" alt="cH4vCV.png"></a></p>
</li>
</ul>
<h4 id="最低松弛度优先-Least-Laxity-First"><a href="#最低松弛度优先-Least-Laxity-First" class="headerlink" title="最低松弛度优先(Least Laxity First)"></a>最低松弛度优先(Least Laxity First)</h4><p><strong>松弛度 = 必须完成时间 - 本身运行时间 - 当前时间</strong></p>
<p>该算法<strong>按松弛度排序实时任务的就绪队列</strong>，松弛度值最小的任务排在队列最前面，调度程序总是选择就绪队列中的队首任务执行。</p>
<p><a href="https://imgtu.com/i/cbmHED"><img src="https://z3.ax1x.com/2021/04/21/cbmHED.png" srcset="/img/loading.gif" alt="cbmHED.png"></a></p>
<p><a href="https://imgtu.com/i/cbmbUe"><img src="https://z3.ax1x.com/2021/04/21/cbmbUe.png" srcset="/img/loading.gif" alt="cbmbUe.png"></a></p>
<ul>
<li><p>在刚开始时(t1 = 0)，A1必须在20 ms 时完成，而它本身运行又需 10 ms，可算出A1的松弛度为10 ms；B1必须在50 ms 时完成，而它本身运行就需25 ms，可算出B1的松弛度为25 ms，故调度程序应先调度A1执行。</p>
</li>
<li><p>在<em>t</em>2 = 10 ms 时，A2的松弛度可按下式算出：<br>A2的松弛度 = 必须完成时间 - 其本身的运行时间 - 当前时间</p>
<pre><code>                 = 40 ms-10 ms-10 ms = 20 ms
</code></pre>
<p>类似地，可算出B1的松弛度为15 ms，故调度程序应选择B2运行。</p>
</li>
<li><p>在t3 = 30 ms 时，A2的松弛度已减为0(即40 - 10 - 30)，而B1的松弛度为15 ms(即50 - 5 - 30)，于是调度程序应抢占B1的处理机而调度A2运行。</p>
</li>
<li><p>。在<em>t</em> 4 = 40 ms时，A3的松弛度为10 ms(即60 - 10 - 40)，而B1的松弛度仅为5 ms(即50 - 5 - 40)，故又应重新调度B1执行。</p>
</li>
<li><p>在t5 = 45 ms 时，B1执行完成，而此时A3 的松弛度已减为5 ms(即60 - 10 - 45)，而B2 的松弛度为30 ms(即100 - 25 - 45)，于是又应调度A3执行。</p>
</li>
<li><p>在t6 = 55 ms 时，任务A 尚未进入第4 周期，而任务B 已进入第2 周期，故再调度B2执行。</p>
</li>
<li><p>在t7 = 70 ms 时，A4的松弛度已减至0 ms(即80 - 10 - 70)，而B2的松弛度为20 ms(即100 - 10 - 70)，故此时调度又应抢占B2的处理机而调度A4 执行。</p>
</li>
<li><p>注意：</p>
<ul>
<li><p><strong>当等待任务的松弛度值为0时才进行抢占（如20ms时虽然A2的松弛度比B1的松弛度小，但A2并没有抢占B1）。</strong></p>
</li>
<li><p>当有任务执行时，只有等待任务的松弛度值为0才会发生任务的调度，其他情况不发生调度。</p>
</li>
<li><p><strong>任务执行结束后或无任务执行时，再比较等待任务的松弛度值，较小的先执行。</strong></p>
</li>
</ul>
</li>
</ul>
<h2 id="3-5-产生死锁的原因和条件"><a href="#3-5-产生死锁的原因和条件" class="headerlink" title="3.5 产生死锁的原因和条件"></a>3.5 产生死锁的原因和条件</h2><p>所谓<strong>死锁（Deadlock）</strong>，是指多个进程在运行过程中因争夺资源而造成的一种僵局（<strong>Deadly- Embrace</strong>），当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。</p>
<h3 id="3-5-1-资源问题"><a href="#3-5-1-资源问题" class="headerlink" title="3.5.1 资源问题"></a>3.5.1 资源问题</h3><ul>
<li><p><strong>可重用性资源</strong></p>
<ul>
<li>每一个可重用资源中的单元只能分配给一个进程使用，不允许多个进程共享</li>
<li>进程在使用该类资源过程中，须按照下列顺序：请求，使用，释放</li>
<li>系统中每一类可重用资源中的单元数目是相对固定的，进程在运行期间既不能创建也不能删除它</li>
</ul>
</li>
<li><p><strong>可消耗性资源</strong></p>
<p>临时性资源，其在进程运行期间，由进程动态地创建和消耗的</p>
<ul>
<li>每一类可消耗性资源的单元数目在运行期间是不断变化的</li>
<li>进程在运行过程中，可以不断地创造可消耗性资源的单元</li>
<li>进程在运行过程中，可以请求若干个可消耗性资源单元</li>
<li>典型：消息</li>
</ul>
</li>
<li><p><strong>可抢占性资源</strong></p>
<ul>
<li><p>某进程在获得这类资源后，该资源可以再被其他进程或系统剥夺</p>
</li>
<li><p>优先权高的进程可以剥夺优先权低的进程的处理机</p>
</li>
<li><p>内存区可由存储器管理程序把一个进程从一个存储区移到另一个存储区，此即剥夺了该进程原来占有的存储区。甚至可将一个进程从内存调出到外存上</p>
</li>
<li><p>CPU和主存均属于可剥夺性资源</p>
</li>
<li><p>多道程序环境下，不会因为竞争可抢占资源而发生死锁。</p>
</li>
</ul>
</li>
<li><p><strong>不可抢占资源</strong></p>
<ul>
<li>当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自行释放</li>
<li>如磁带机、打印机等</li>
</ul>
</li>
</ul>
<h3 id="3-5-2-计算机系统中的死锁"><a href="#3-5-2-计算机系统中的死锁" class="headerlink" title="3.5.2 计算机系统中的死锁"></a>3.5.2 计算机系统中的死锁</h3><ul>
<li>竞争资源。当系统中供多个进程共享的资源如打印机、公用队列等，其数目不足以满足诸进程的需要时，会引起诸进程对资源的竞争而产生死锁。</li>
<li>进程间推进顺序非法。进程在运行过程中，请求和释放资源的顺序不当，也同样会导致产生进程死锁。</li>
</ul>
<h4 id="竞争资源引起的进程死锁"><a href="#竞争资源引起的进程死锁" class="headerlink" title="竞争资源引起的进程死锁"></a>竞争资源引起的进程死锁</h4><ul>
<li><p>竞争不可抢占性(非剥夺性)资源</p>
<ul>
<li><p>在系统中所配置的非剥夺性资源，由于它们的数量不能满足诸进程运行的需要，会使进程在运行过程中，因争夺这些资源而陷入僵局。</p>
</li>
<li><p>例如，系统中只有一台打印机R1和一台磁带机R2，可供进程P1和P2共享。处理不好，在P1与P2之间会形成僵局，引起死锁。</p>
<p>假定P1已占用了打印机R1，P2已占用了磁带机R2。此时，若P2继续要求打印机，P2将阻塞；P1若又要求磁带机，P1也将阻塞。于是，在P1与P2之间便形成了僵局，两个进程都在等待对方释放出自己所需的资源。但它们又都因不能继续获</p>
<p>得自己所需的资源而不能继续推进，从而也不能释放出自己已占有的资源，以致进入死锁状态。</p>
<p>为便于说明，我们用方块代表资源，用圆圈代表进程。当箭头从进程指向资源时，表示进程请求资源；当箭头从资源指向进程时，表示该资源已被分配给该进程。从中可以看出，这时在P1、P2及R1和R2之间已经形成了一个环路，说明已进入死锁状态。</p>
<p><a href="https://imgtu.com/i/cbR0ud"><img src="https://z3.ax1x.com/2021/04/21/cbR0ud.png" srcset="/img/loading.gif" alt="cbR0ud.png"></a></p>
</li>
</ul>
</li>
<li><p>竞争可消耗性(临时性)资源</p>
<ul>
<li><p>永久性资源：可顺序重复使用型资源称为永久性资源。</p>
</li>
<li><p>临时性资源，是指由一个进程产生，被另一进程使用一暂短时间后便无用的资源，故也称之为消耗性资源，它也可能引起死锁。</p>
</li>
<li><p>例如：S1、S2和S3是临时性资源，由进程P1、P2和P3产生的消息。如果消息通信处理顺序不当也会发生死锁。</p>
<p><a href="https://imgtu.com/i/cbWJqs"><img src="https://z3.ax1x.com/2021/04/21/cbWJqs.png" srcset="/img/loading.gif" alt="cbWJqs.png"></a></p>
<p>如果消息通信按下述顺序进行：</p>
<p>P1： …Release(S1)； Reqaest(S3)； …</p>
<p>P2： …Release(S2)； Request(S1)； …</p>
<p>P3： …Release(S3)； Request(S2)； …</p>
<p>并不可能发生死锁，</p>
<p>P1： …Request(S3)； Release(S1)； …</p>
<p>P2： …Request(S1)； Release(S2)； …</p>
<p>P3： …Request(S2)； Release(S3)； …</p>
<p>则可能发生死锁。</p>
</li>
</ul>
</li>
<li><p>进程推进顺序不合法引起死锁</p>
<ul>
<li><p>进程推进顺序合法</p>
<p>进程推进顺序是合法不会引起进程死锁的。 </p>
</li>
<li><p>进程推进顺序非法 </p>
<p>若并发进程P1和P2推进顺序不合法，进入不安全状态，于是发生了进程死锁 。</p>
</li>
<li><p><a href="https://imgtu.com/i/cbfLnJ"><img src="https://z3.ax1x.com/2021/04/21/cbfLnJ.png" srcset="/img/loading.gif" alt="cbfLnJ.png"></a></p>
</li>
</ul>
</li>
</ul>
<h3 id="3-5-3-死锁的必要条件和处理方法"><a href="#3-5-3-死锁的必要条件和处理方法" class="headerlink" title="3.5.3 死锁的必要条件和处理方法"></a>3.5.3 死锁的必要条件和处理方法</h3><p><strong>死锁的定义</strong>：<strong>如果一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的事件</strong>，那么该组的进程是死锁的。(Deadlock)</p>
<p><strong>死锁的发生必须具备下列四个必要条件：</strong></p>
<ul>
<li><p><strong>互斥条件</strong>。指进程对所分配到的资源进行排它性使用。</p>
</li>
<li><p><strong>请求和保持条件</strong>。指进程已经保持了至少一个资源，但又提出了新的资源请求 ，而该资源已被其他进程占用，此时进程被阻塞，但对自己获得的资源保持不放。</p>
</li>
<li><p><strong>不剥夺条件</strong>。指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。</p>
</li>
<li><p><strong>环路等待条件</strong>。在发生死锁时，必然存在一个<strong>进程——资源的环形链</strong> </p>
</li>
</ul>
<h4 id="处理方法"><a href="#处理方法" class="headerlink" title="处理方法"></a>处理方法</h4><ul>
<li><p><strong>预防死锁</strong>：破坏产生死锁的四个必要条件中的一个或几个条件。</p>
</li>
<li><p><strong>避免死锁</strong>：用某种方法去防止系统进入不安全状态。 </p>
<p>在资源的动态分配过程中进行。</p>
</li>
<li><p><strong>检测死锁</strong>：及时地检测出死锁的发生，确定有关的进程和资源。</p>
</li>
<li><p><strong>解除死锁</strong>：撤消或挂起一些进程。</p>
</li>
</ul>
<h2 id="3-6-预防死锁"><a href="#3-6-预防死锁" class="headerlink" title="3.6 预防死锁"></a>3.6 预防死锁</h2><p>预防死锁的方法是使四个必要条件中的第2、3、4条件之一不能成立，来避免发生死锁。</p>
<p>至于必要条件1，因为它是由设备的固有属性所决定的，不仅不能改变，还应加以保证。</p>
<h3 id="3-6-1-摒弃“请求和保持”条件"><a href="#3-6-1-摒弃“请求和保持”条件" class="headerlink" title="3.6.1 摒弃“请求和保持”条件"></a>3.6.1 摒弃“请求和保持”条件</h3><p>系统规定所有进程在开始运行之前，<strong>都必须一次性地申请其在整个运行过程所需的全部资源</strong>。这样，该进程在整个运行期间：便不会再提出资源要求，从而摒弃了请求和保持条件，从而可以避免发生死锁。</p>
<p>这种预防死锁的方法的优点：简单、易于实现且很安全。</p>
<p>缺点：资源被严重浪费，出现饥饿现象，使进程延迟运行。</p>
<h3 id="3-6-2-摒弃“不剥夺”条件"><a href="#3-6-2-摒弃“不剥夺”条件" class="headerlink" title="3.6.2 摒弃“不剥夺”条件"></a>3.6.2 摒弃“不剥夺”条件</h3><p>进程是逐个地提出对资源的要求的。<strong>当一个已经保持了某些资源的进程，再提出新的资源请求而不能立即得到满足时，必须释放它已经保持了的所有资源。</strong>待以后需要时再重新申请。从而摒弃了“不剥夺”条件。</p>
<p>这种预防死锁的方法，实现起来比较复杂且要付出很大代价。因为一个资源在使用一段时间后，它的被迫释放可能会造成前段工作的失效。还会使进程前后两次运行的信息不连续 。</p>
<h3 id="3-6-3-摒弃“环路等待”条件"><a href="#3-6-3-摒弃“环路等待”条件" class="headerlink" title="3.6.3 摒弃“环路等待”条件"></a>3.6.3 摒弃“环路等待”条件</h3><p>这种方法中规定，系统<strong>将所有资源按类型进行线性排队，并赋予不同的序号</strong>。 <strong>所有进程对资源的请求必须严格按照资源序号递增的次序提出</strong>，这样，在所形成的资源分配图中，不可能再出现环路，因而摒弃了“环路等待”条件。</p>
<ul>
<li>存在的问题：<ul>
<li>首先是为系统中各类资源所分配（确定）的序号，必须相对稳定，这就限制了新类型设备的增加</li>
<li>作业（进程）使用各类资源的顺序，与系统规定的顺序不同，造成对资源的浪费 </li>
<li>限制用户简单、自主地编程 。</li>
</ul>
</li>
</ul>
<h2 id="3-7-避免死锁"><a href="#3-7-避免死锁" class="headerlink" title="3.7 避免死锁"></a>3.7 避免死锁</h2><h3 id="3-7-1-系统安全状态"><a href="#3-7-1-系统安全状态" class="headerlink" title="3.7.1 系统安全状态"></a>3.7.1 系统安全状态</h3><ul>
<li><p>定义：所谓安全状态，是指系统能按某种进程顺序（P1，P2，…，Pn），来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成，称系统处于<strong>安全状态</strong>，称〈P1，P2，…，Pn〉序列为<strong>安全序列</strong> 。否则<strong>，如果系统无法找到这样一个安全序列，则称系统处于不安全状态</strong>。（找到一个序列即可）</p>
</li>
<li><p>安全状态实例</p>
<p>假定系统中有三个进程P1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0** 时刻进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，在T0时刻系统是否安全？</p>
<p>&lt;P2,P1,P3&gt;,安全。</p>
</li>
<li><p><strong>由安全状态向不安全状态的转换</strong></p>
<p><strong>不按照安全序列分配资源</strong></p>
</li>
</ul>
<h3 id="3-7-2-利用银行家算法避免死锁"><a href="#3-7-2-利用银行家算法避免死锁" class="headerlink" title="3.7.2 利用银行家算法避免死锁"></a>3.7.2 利用银行家算法避免死锁</h3><p>银行家算法（！！！）</p>
<p>最有代表性的避免死锁的算法，是<strong>Dijkstra 的银行家算法</strong>。这是由于该算法能用于银行系统现金贷款的发放而得名的。为实现银行家算法，系统中必须设置若干数据结构。</p>
<h4 id="银行家算法中的数据结构"><a href="#银行家算法中的数据结构" class="headerlink" title="银行家算法中的数据结构"></a>银行家算法中的数据结构</h4><ul>
<li><p><strong>可利用资源向量</strong>Available：这是一个含有m个元素的数组，其中的每一个元素代表一类<strong>可利用的资源数目</strong>。其数值随该类资源的分配和回收而动态地改变。</p>
</li>
<li><p><strong>最大需求矩阵</strong>Max：这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的<strong>最大需求</strong>。如果Max[i,j]=K，则表示进程i需要Rj类资源的最大数目为K。</p>
</li>
<li><p><strong>分配矩阵</strong>Allocation：这是一个n×m的矩阵，它定义了系统中每一类资源当前<strong>已分配</strong>给每一进程的资源数。如果Allocation[ i,j ]=K，则表示进程Pi当前已分得Rj类资源的数目为K。</p>
</li>
<li><p><strong>需求矩阵</strong>Need：这也是一个n×m的矩阵，用以表示每一个进程<strong>尚需</strong>的各类资源数。如果Need[ i,j ]=K，则表示进程Pi还需要Rj类资源K个，方能完成其任务。</p>
<p><strong>Need[ i,j ] ＝ Max[ i,j ]  -  Allocation[ i,j ]</strong></p>
</li>
</ul>
<h4 id="银行家算法"><a href="#银行家算法" class="headerlink" title="银行家算法"></a>银行家算法</h4><p>设Requesti，是进程Pi的请求向量，当Pi发出资源请求后，系统按下述步骤进行检查：</p>
<ul>
<li><p>如果Requesti[ j ] ≤ Need[ i,j ], 便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。</p>
</li>
<li><p>如果Requesti[ j ] ≤ Available[ j ]，便转向步骤（3）；否则，表示尚无足够资源，Pi须等待。</p>
</li>
<li><p>系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：</p>
<p>Available[ j ] = Available[ j ] — Requesti[ j ]；</p>
<p>Allocation[ i,j ] =  Allocation[ i,j ] + Requesti[ j ];</p>
<p>​    Need[ i, j ] = Need[ i, j ] - Requesti[ j ]；</p>
</li>
<li><p>系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。</p>
</li>
</ul>
<h4 id="安全性算法"><a href="#安全性算法" class="headerlink" title="安全性算法"></a>安全性算法</h4><p>  （1） 设置两个向量：</p>
<p>①工作向量Work: <strong>它表示系统可提供给进程继续运行所需的各类资源数目，Work =  Available</strong></p>
<p>②Finish：开始时先做Finish[i] = false；当有足够资源分配给进程时，再令Finish[i] = true。</p>
<p>（2）从进程集合中找到一个能满足下述条件的进程：</p>
<p>   ①Finish[i] = false；</p>
<p>   ②Need[i,j] ≤ work[j]；</p>
<p>   找到，执行步骤（3)；否则，执行步骤（4）。</p>
<p>（3）当进程只获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：</p>
<p>​    Work[ j ] = Work[ i ] + Allocation[ i,j ]；</p>
<p>​    Finish[ i ] = true; </p>
<p>​    go to step 2</p>
<p> （4）如果所有进程的Finish[i]＝true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。</p>
<h4 id="例题"><a href="#例题" class="headerlink" title="例题"></a>例题</h4><h2 id="3-8-死锁的检测与解除"><a href="#3-8-死锁的检测与解除" class="headerlink" title="3.8 死锁的检测与解除"></a>3.8 死锁的检测与解除</h2><h3 id="3-8-1-死锁的检测"><a href="#3-8-1-死锁的检测" class="headerlink" title="3.8.1 死锁的检测"></a>3.8.1 死锁的检测</h3><p>当系统为进程分配资源时，若未采取任何限制性措施，则系统必须提供检测和解除死锁的手段。</p>
<h4 id="资源分配图"><a href="#资源分配图" class="headerlink" title="资源分配图"></a>资源分配图</h4><p>该图是由一组结点N和一组边E所组成的一个对偶G＝（N,E）。其中：</p>
<ul>
<li><p>把N分为两个互斥的子集，即一组进程结点P={P1,P2，…，Pn）和一组资源结点R={r1, r2, …, rn}，N＝PUR。 </p>
</li>
<li><p>凡属于E中的一个边e∈ E都连接着P中的一个结点和R中的一个结点。</p>
<ul>
<li><p>e＝{Pi,rj} </p>
<p>它表示进程pj请求一个单位的rj资源。</p>
<p>e={rj，Pi}   </p>
<p>  它表示把一个单位的资源rj分配给进程Pi。 </p>
</li>
<li><p><a href="https://imgtu.com/i/cbT5N9"><img src="https://z3.ax1x.com/2021/04/21/cbT5N9.png" srcset="/img/loading.gif" alt="cbT5N9.png"></a></p>
<p>我们用圆圈代表一个进程，用方框代表一类资源。由于一种类型的资源可能有多个，我们用方框中的一个点代表一类资源中的一个资源。此时，请求边是由进程指向方框中的rj，而分配边则应始于方框中的一个点。图3-20 示出了一个资源分配图。图中，p1进程已经分得了两个r1资源，并又请求一个r2资源；p2进程分得了一个r1和一个r2资源，并又请求r1资源。</p>
</li>
</ul>
</li>
</ul>
<h4 id="死锁定理"><a href="#死锁定理" class="headerlink" title="死锁定理"></a>死锁定理</h4><p>S为死锁状态的<strong>充分条件</strong>是：当且仅当S状态的资源分配图是<strong>不可完全简化的</strong>。该充分条件被称为死锁定理。</p>
<p><a href="https://imgtu.com/i/cb7BDO"><img src="https://z3.ax1x.com/2021/04/21/cb7BDO.png" srcset="/img/loading.gif" alt="cb7BDO.png"></a></p>
<ul>
<li><p>在资源分配图中，找出一个既不阻塞又非独立的进程结点Pi。在顺利的情况下，Pi可获得所需资源而继续运行，直至运行完毕，再释放其所占有的全部资源，这相当于消去pi所求的请求边和分配边，使之成为孤立的结点。在图3-21(a)中，将p1的两个分配边和一个请求边消去，便形成图(b)所示的情况。</p>
</li>
<li><p>p1释放资源后，便可使p2获得资源而继续运行，直至p2完成后又释放出它所占有的全部资源，形成图(c)所示的情况。</p>
</li>
<li><p>在进行一系列的简化后，若能消去图中所有的边，使所有的进程结点都成为孤立结点，则称该图是可完全简化的；若不能通过任何过程使该图完全简化，则称该图是不可完全简化的。</p>
</li>
</ul>
<p>对于较复杂的资源分配图，可能有多个既未阻塞，又非孤立的进程结点，不同的简化顺序是否会得到不同的简化图？有关文献已经证明，<strong>所有的简化顺序，都将得到相同的不可简化图。</strong>同样可以证明：S为死锁状态的充分条件是：当且仅当S状态的资源分配图是不可完全简化的。该充分条件被称为死锁定理。</p>
<h4 id="死锁检测中的数据结构"><a href="#死锁检测中的数据结构" class="headerlink" title="死锁检测中的数据结构"></a>死锁检测中的数据结构</h4><p>（1）可利用资源向量Available，它表示了m类资源中每一类资源的可用数目。</p>
<p>（2）把不占用资源的进程（Allocation：=0）记入L表中，即Li U L</p>
<p>（3）从进程集合中找到一个Requesti≤work的进程，做如下处理：</p>
<p>​     ① Work :＝ Work + Allocationi，</p>
<p>​     ②将它记入L表中。</p>
<p>（4）<strong>若不能把所有进程都记入L表中，便表明系统状态S的资源分配图是不可完全简化的。</strong>因此，该系统状态将发生死锁。</p>
<h3 id="3-8-2-解除死锁"><a href="#3-8-2-解除死锁" class="headerlink" title="3.8.2 解除死锁"></a>3.8.2 解除死锁</h3><p>当发现有进程死锁时，常采用的两种方法是解除死锁：</p>
<ul>
<li><strong>剥夺资源</strong>。从其它进程剥夺足够数量的资源给死锁进程，以解除死锁状态。</li>
<li><strong>撤消进程</strong>。最简单的撤消进程的方法，是使全部死锁进程都夭折掉；或者按照某种顺序逐个地撤消进程，直至有足够的资源可用，使死锁状态消除为止。</li>
</ul>
<h1 id="第四章-存储器管理"><a href="#第四章-存储器管理" class="headerlink" title="第四章 存储器管理"></a>第四章 存储器管理</h1><p>存储器管理的对象主要是内存，由于对外存的管理与对内存的管理类似，只是用途不同（外存主要用于存放文件），所以我们把对外存的管理放在文件管理中介绍。</p>
<ul>
<li><strong>课程提要</strong><ul>
<li>存储器的层次结构</li>
<li>程序的装入和链接</li>
<li>连续分配存储管理方式</li>
<li>基本分页式存储管理方式</li>
<li>基于分段式存储管理方式</li>
<li>虚拟存储器概念</li>
<li>请求分页存储管理方式</li>
<li>抖动与工作集</li>
<li>请求分段存储管理方式</li>
</ul>
</li>
</ul>
<h2 id="4-1-存储器的层次结构"><a href="#4-1-存储器的层次结构" class="headerlink" title="4.1 存储器的层次结构"></a>4.1 存储器的层次结构</h2><h3 id="4-1-1-多层结构的存储器系统"><a href="#4-1-1-多层结构的存储器系统" class="headerlink" title="4.1.1 多层结构的存储器系统"></a>4.1.1 多层结构的存储器系统</h3><p><a href="https://imgtu.com/i/gCf0HI"><img src="https://z3.ax1x.com/2021/04/27/gCf0HI.png" srcset="/img/loading.gif" alt="gCf0HI.png"></a></p>
<p><strong>可执行存储器：寄存器和主存储器</strong></p>
<p>对于存放于可执行存储器和辅存的信息，计算机所采用的访问机制是不同的，所耗费的时间也是不同的，进程可以在很少的时间周期内使用一条load或store指令对可执行存储器进行访问；但对辅存的访问则需要通过I/O设备实现，访问中涉及到中断、设备驱动程序以及物理设备的运行，所耗费的时间远高于访问可执行存储器的时间，一般相差3个数量级。</p>
<ul>
<li><p>主存储器(内存、主存、可执行存储器)</p>
<p>用于保存进程运行时的程序和数据。CPU的控制部件只能从主存中取得指令和数据到CPU寄存器，同样，CPU寄存器中的数据可存入主存。<br>CPU与外设交换数据必须依托主存。</p>
<p>由于主存储器访问速度远低于CPU执行指令的速度，为缓和这一矛盾，在计算机系统中引入寄存器和高速缓存。</p>
<p><strong>用户的程序在运行时应存放在主存中，以便处理机访问</strong></p>
<p>由于主存容量和速度有限。所以把那些不马上使用的程序、数据放在外部存储器(又称辅存)中。当用到时再把它们读入主存。</p>
</li>
<li><p>寄存器</p>
<p>寄存器具有与处理机相同的速度，故对寄存器的访问速度最快，完全能与CPU协同工作，只是价格高昂。</p>
</li>
<li><p>高速缓存</p>
<p>CPU对高速缓存的访问，其速度比访问主存快，比访问寄存器慢。它介于寄存器和存储器之间，主要用于备份主存中比较常用的数据，用于缓和内存与处理机速度之间的矛盾。</p>
<p>根据<strong>程序执行的局部性原理</strong>，将主存中一些经常访问的数据存放在高速缓存中，减少访问主存的次数，提高程序的执行速度。</p>
<p>有些计算机系统设置了两级高速缓存，即，一级高速缓存与二级高速缓存。</p>
</li>
<li><p>磁盘缓存</p>
<p>使用目的：磁盘的I/O速度远低于对主存的访问速度，为缓和二者速度上的不匹配，设置了磁盘缓冲器，主要用于存放频繁使用的一部分磁盘数据和信息，以减少访问磁盘的次数。<br><strong>但与高速缓存不同，磁盘缓存本身不是一种实际存在的存储器，而是利用主存中的部分存储空间暂时存放从磁盘存读出/写入的信息。</strong>（利用主存实现）</p>
<p>辅存的数据必须复制到主存才能使用，数据也必须先存放于主存，才能输出到外存。</p>
</li>
</ul>
<h3 id="4-1-2-存储器管理的目的和功能"><a href="#4-1-2-存储器管理的目的和功能" class="headerlink" title="4.1.2 存储器管理的目的和功能"></a>4.1.2 存储器管理的目的和功能</h3><p>1.主存储器的分配和管理<br>按用户要求把适当的存储空间分配给相应的作业。一个有效的存储分配机制，应在用户请求时能作出快速的响应，分配相应的存储空间；在用户不再使用它时，应立即回收，以供其他用户使用。</p>
<p>为此，这个存储分配机制应具有如下3个<strong>功能</strong>：</p>
<ul>
<li>记住每个存储区域的状态：哪些是已经分配的，哪些是可以用作分配的。</li>
<li>实施分配：在系统或用户提出申请时，按所需的量给予分配；修改相应的分配记录表。</li>
<li>接受系统或用户释放的存储区域：并相应地修改分配记录表。</li>
</ul>
<p>为了便于对主存储器进行有效的管理，我们把存储器分成若干个区域。即使在最简单的单用户系统中，至少也要把它分成两个区域：在一个存储区域内存放<strong>系统软件</strong>，如操作系统本身；而另一个存储区域则用于安置<strong>用户作业</strong>。显然，在多用户系统中，为了提高系统的利用率，需要将存储器划分成更多的区域，以便同时存放多个用户作业。这就引起了存储器分配问题及随之产生的其它问题。</p>
<p>2.提高主存储器的利用率：使多道程序能动态地共享主存，最好能共享主存，最好能共享主存中的信息。</p>
<p>3.“扩充”主存储器容量：借助于提供虚拟存储器或其他自动覆盖技术来达到、即<strong>为用户提供比主存储器空间还大的地址空间</strong>。</p>
<p>4.存储保护：确保各道作业都在所分配的存储区域内操作，互不干扰。即要防止一道作业由于发生错误而损害其他作业，特别需要防止破坏其中的系统程序。这个问题不能使用特权指令来加以解决，而必须提供<strong>硬件保护</strong>功能，由<strong>软件配合</strong>实现。</p>
<h3 id="4-1-3-存储分配的三种方式"><a href="#4-1-3-存储分配的三种方式" class="headerlink" title="4.1.3 存储分配的三种方式"></a>4.1.3 存储分配的三种方式</h3><p>存储分配：解决多道作业之间共享主存的问题。<br>解决的问题：确定什么时候，以什么方式，把一个作业的全部信息/作业运行时首先需要的信息分配到主存，并使这些问题对于用户而言尽可能“透明”。</p>
<p>解决存储分配的三种方式：<br><strong>1.直接指定方式</strong></p>
<ul>
<li>程序员在编程的时候，或编译程序（汇编程序）对源程序进行编译（汇编）时，使用实际存储地址。<ul>
<li>在多道程序环境下，应保证各作业所用的地址互不重叠。</li>
</ul>
</li>
<li>采用<strong>直接指定方式分配的前提</strong>是：存储器的可用容量（空间）已经给定或者可以指定，这对单用户计算机系统是不成问题的。</li>
<li>在多道程序发展初期，通常把存储空间划分成若干个固定的不同大小分区，并对不同的作业指定相应的分区。因此，对编程人员或者编译程序而言，存储器的可用空间是可知的。</li>
<li>这种分配方式的实质：由编程人员在编写程序时，或由编程程序编译源程序时，对一个作业的所有信息确定在主存存储空间中的位置。因此，这种直接指定方式的存储方案，不仅<strong>用户感到不便，而且存储空间的利用也不那么有效</strong>。（缺点）</li>
</ul>
<p><strong>2.静态分配方式（Static Allocation）</strong></p>
<p>用户在编程时，或由编译程序产生的目的程序，均可从其地址空间的零地址开始；当装配程序对其进行链接装入时才确定它们在主存中的相应位置，从而生成可执行程序。也就是说，<strong>存储分配是在装入时实现</strong>的。</p>
<ul>
<li>静态分配方式特点：<ul>
<li>在一个作业装入时必须分配其要求的全部存储量</li>
<li>如果没有足够的存储空间，就不能装入该作业</li>
<li>一旦一个作业进入内存后，在其退出系统之前，它一直占用着分配给它的全部存储空间</li>
<li>作业在整个运行过程中不能在内存中“搬家”、也不能再申请存储空间（<strong>没有扩展性、可移植性</strong>）</li>
</ul>
</li>
</ul>
<p>静态分配策略的存储管理很简单，但在多道程序系统中不能有效地共享存储器资源。</p>
<p><strong>3.动态分配方式(Dynamic Allocation)</strong></p>
<p>一种更加有效的使用主存储器的方法。</p>
<ul>
<li><p>动态存储分配方式的特点：</p>
<ul>
<li><p>作业在存储空间中的位置，也是在装入时确定的</p>
</li>
<li><p>在其执行过程中，可根据需要申请附加的存储空间（可扩展性）</p>
</li>
<li><p>一个作业已占用的<strong>部分存储区域不再需要时，可以要求归还给系统</strong></p>
<p>即：这种存储分配机制能接受不可预测的分配和释放存储区域的请求，实现个别存储区域的分配和回收</p>
</li>
<li><p>存储区域的大小是可变的</p>
</li>
<li><p>允许作业在内存中“搬家”（可扩展性）</p>
</li>
</ul>
<p>目前，<strong>绝大多数计算机系统都采用静态或动态存储分配方式</strong>，所以，在本章只讨论这两种存储分配的实现技术，重点放在各种动态存储分配技术的实现上。</p>
</li>
</ul>
<h3 id="4-1-4-基本概念"><a href="#4-1-4-基本概念" class="headerlink" title="4.1.4 基本概念"></a>4.1.4 基本概念</h3><ul>
<li><p>逻辑地址（相对地址、虚地址）</p>
<p>用户的程序经过汇编或编译后形成目标代码，<strong>目标代码通常采用相对地址的形式</strong>，其<strong>首地址为0，其余指令中的地址都相对于首地址而编址</strong>。</p>
<p>注意：不能用逻辑地址在内存中读取信息。</p>
</li>
<li><p>物理地址（绝对地址、实地址）</p>
<p>内存中存储单元的地址，可以直接寻址。</p>
</li>
<li><p>名空间：一个用高级语言编制的源程序，我们说它存在于由程序员建立的符号名字空间（简称名空间）</p>
</li>
<li><p>地址空间：程序用来访问信息所用地址单元的集合，是<strong>逻辑（相对）地址集合</strong>，由<strong>编译程序</strong>生成</p>
</li>
<li><p>存储空间：<strong>主存中物理单元的集合</strong>。这些单元的编号称物理地址或绝对地址。存储空间的大小是由主存的实际容量决定的。</p>
</li>
</ul>
<p>在用汇编语言或高级语言编写的程序中，是通过符号名来访问子程序和数据的。把程序中符号名的集合叫做“名字空间”。汇编语言源程序经过汇编，或者高级语言源程序经过编译，得到的目标程序是以0作为参考地址的模块。<strong>然后多个目标模块由连接程序连接成一个具有统一地址的装配模块，以便最后装入内存中执行</strong>。把<strong>目标模块中的地址称为相对地址</strong>，而把相对地址的集合叫做“地址空间”。</p>
<p><a href="https://imgtu.com/i/RMwS9H"><img src="https://z3.ax1x.com/2021/06/24/RMwS9H.png" srcset="/img/loading.gif" alt="RMwS9H.png"></a></p>
<h2 id="4-2-程序的装入和链接"><a href="#4-2-程序的装入和链接" class="headerlink" title="4.2 程序的装入和链接"></a>4.2 程序的装入和链接</h2><p>在多道程序环境下，程序要运行必须为之创建进程，而创建进程的第一件事情就是要把用户编写好的源程序和数据装入内存。如何将一个用户源程序变为一个可在内存中执行的程序，通常要经过下列几步：</p>
<ul>
<li>编译：<strong>源程序模块</strong>是用高级语言或汇编语言写的一组程序语句。计算机不能直接执行源语句，它们要首先被编译程序或解释程序翻译成机器级代码。<strong>编译程序</strong>(Compiler)接受完整的源一级的程序，并以类似于成批的方式生成完整的<strong>目标一级的模块</strong>。</li>
<li> 链接(Linker)：<strong>目标模块</strong>是纯二进制的机器级代码。计算机可以执行目标级代码，但是典型的目标模块是不完备的，它包含对其它目标模块（诸如存取方法或子例程）或库函数的引用。因此，<strong>目标模块通常是不能装入计算机并执行的</strong>。</li>
<li>装入（loader）：由装入程序将装入模块装入内存并执行。</li>
</ul>
<p><a href="https://imgtu.com/i/RMwIVf"><img src="https://z3.ax1x.com/2021/06/24/RMwIVf.png" srcset="/img/loading.gif" alt="RMwIVf.png"></a></p>
<h3 id="4-2-1-程序的装入"><a href="#4-2-1-程序的装入" class="headerlink" title="4.2.1 程序的装入"></a>4.2.1 程序的装入</h3><p>根据存储空间的分配方式，将一个装入模块装入内存时，可采用三种方式：</p>
<ul>
<li><p>绝对装入方式(Absolute Loading Mode) </p>
<p>在编译时，如果知道程序将驻留在内存的具体位置，那么编译程序将产生实际存储地址（绝对地址）的目标代码</p>
</li>
<li><p>可重定位装入方式(Relocation Loading Mode)</p>
</li>
<li><p>动态运行时装入方式(Denamle Run-time Loading)</p>
</li>
</ul>
<h4 id="4-2-1-1-绝对装入方式"><a href="#4-2-1-1-绝对装入方式" class="headerlink" title="4.2.1.1 绝对装入方式"></a>4.2.1.1 绝对装入方式</h4><p>装入程序按照装入模块中的地址，将程序和数据装入内存。装入模块被装入内存后，由于程序中的<strong>逻辑地址与实际存储地址完全相同</strong>，所以<strong>不需要对程序和数据的地址进行修改</strong>。</p>
<p>程序中所使用的<strong>绝对地址既可以在编译或汇编时给出，也可以由程序员直接赋予</strong>。但是通常在程序中采用<strong>符号地址</strong>，然后在编译或汇编时，再将这些符号地址转换为绝对地址。</p>
<h4 id="4-2-1-2-可重定位装入方式"><a href="#4-2-1-2-可重定位装入方式" class="headerlink" title="4.2.1.2 可重定位装入方式"></a>4.2.1.2 可重定位装入方式</h4><ul>
<li><p>重定位（地址映射/地址转换）</p>
<ul>
<li><p>经编译得到的目标模块中为相对地址（通常从0开始），即地址都是相对于0开始的。</p>
</li>
<li><p><strong>装入模块中的逻辑地址与实际装入内存的物理地址不同</strong></p>
</li>
<li><p><strong>装入内存</strong>时，相对地址（数据、指令地址）要作出相应的修改以得到正确的物理地址，这个修改的过程称为<strong>重定位</strong></p>
<p>重定位就是把程序的逻辑地址空间变换成内存中的实际物理地址空间的过程，也就是说在装入时对目标程序中指令和数据的修改过程。</p>
</li>
</ul>
</li>
<li><p>根据<strong>地址变换进行的时间</strong>及<strong>采用技术手段</strong>不同：</p>
<ul>
<li><p>静态重定位</p>
<ul>
<li><p>地址变换是在装入内存时一次完成的，且以后不能移动</p>
</li>
<li><p>一般情况下有：</p>
<p> 物理地址=相对地址 + 内存中的起始地址</p>
</li>
<li><p>适用于<strong>多道程序环境</strong>，可将装入模块装入到内存中任何允许的位置</p>
</li>
<li><p>数据地址和指令地址都需要做同样的修改</p>
</li>
<li><p>优点：不需要硬件支持，可以装入有限多道程序</p>
<p>缺点：一个程序通常要占用连续的内存空间，<strong>程序装入内存后不能移动，不易实现共享</strong></p>
</li>
</ul>
</li>
<li><p>动态重定位</p>
</li>
</ul>
</li>
</ul>
<h4 id="4-2-1-3-动态运行时装入方式"><a href="#4-2-1-3-动态运行时装入方式" class="headerlink" title="4.2.1.3 动态运行时装入方式"></a>4.2.1.3 动态运行时装入方式</h4><p>装入程序将装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种<strong>地址转换推迟到程序执行时进行</strong>。在<strong>硬件地址变换机构</strong>的支持下，随着对每条指令或数据的访问<strong>自动</strong>进行地址变换，故称为动态重定位。</p>
<ul>
<li><p>最简单的办法是利用一个<strong>重定位寄存器(RR)**。该寄存器的值是</strong>由进程调度程序根据作业分配到的存储空间起始地址来设定**的。</p>
</li>
<li><p>在具有这种地址变换机构的计算机系统中，当执行作业时，不是根据CPU给出的有效地址去访问主存，而是将有效地址与重定位寄存器中的内容相加后得到的地址作为访问主存的地址。</p>
<p>有效地址 = 重定位寄存器内容 + 相对地址</p>
</li>
<li><p>由于这种地址变换是在作业执行期间随着每条指令的数据自动地、连续地进行，所以称之为动态重定位。</p>
</li>
</ul>
<p>采用动态重定位技术后，程序中所有指令和数据的实际地址是在运行过程中最后访问的时刻确定的。也就是说<strong>，在作业运行过程中临时申请分配附加的存储区域或释放已占用的部分存储空间是允许的</strong>。</p>
<ul>
<li><p>主要优点：</p>
<p>​    ①主存的使用更加灵活有效。这里，<strong>一个用户的作业不一定要分配在一个连续的存储区</strong>，因而可以使用较小的分配单位。而且，在作业开始之前也不一定把它的地址空间全部装入主存，而<strong>可在作业执行期间响应请求动态地进行分配</strong>。</p>
<p>​    ②几个作业<strong>共享</strong>一程序段的单个副本比较容易。</p>
<p>​    ③<strong>有可能向用户提供一个比主存的存储空间大得多的地址空间</strong>。因而无需用户来考虑覆盖结构，而由系统来负责全部的存储管理。</p>
</li>
<li><p>主要缺点：</p>
<p>①需要附加<strong>硬件支持</strong>；</p>
<p>②实现存储器管理的软件比较<strong>复杂</strong>。</p>
</li>
</ul>
<h3 id="4-2-2-程序的链接"><a href="#4-2-2-程序的链接" class="headerlink" title="4.2.2 程序的链接"></a>4.2.2 程序的链接</h3><p><strong>链接程序的功能：将经过编译后所得到的一组目标模块以及它们所需要的库函数，装配成一个完整的装入模块。</strong></p>
<p>根据<strong>链接时间</strong>的不同，可把链接分成如下三种：</p>
<ul>
<li>静态链接(Static Linking) </li>
<li>装入时动态链接(Load-Time Dynamic Linking)</li>
<li>运行时动态链接(Run-Time Dynamic Linking)</li>
</ul>
<h4 id="4-2-2-1-静态链接"><a href="#4-2-2-1-静态链接" class="headerlink" title="4.2.2.1 静态链接"></a>4.2.2.1 静态链接</h4><ul>
<li>说明：将几个目标链接装配成一个装入模块时，需解决以下两个问题：<ul>
<li>将相对地址进行修改。即将除第一个模块外的相对地址修改成装入模块中的相应的相对地址。</li>
<li>变换外部调用符号。即将每个模块中所用的外部调用符号，都变换为相对地址。例如将call B变换为JSR “L”</li>
</ul>
</li>
</ul>
<p>​     <strong>这种先进行链接所形成的一个完整的装入模块，又称为可执行文件</strong>。</p>
<h4 id="4-2-2-2-装入时动态链接"><a href="#4-2-2-2-装入时动态链接" class="headerlink" title="4.2.2.2 装入时动态链接"></a>4.2.2.2 装入时动态链接</h4><p>用户源程序经编译后所得到的目标模块，是在<strong>装入内存时，边装入边链接的</strong>。<strong>即在装入一个目标模块时，若发生一个外部模块调用，将引起装入程序去找出相应的外部目标模块，并将其装入内存</strong>。</p>
<ul>
<li>优点：<ul>
<li><strong>便于软件版本的修改和更新。</strong>只需修改各个目标模块，不必将装入模块拆开，非常方便。</li>
<li><strong>便于实现目标模块共享。</strong>即可以<strong>将一个目标模块链接到几个应用模块中</strong>，从而实现多个应用程序对该模块的共享。</li>
</ul>
</li>
</ul>
<p><a href="https://imgtu.com/i/RMfBSx"><img src="https://z3.ax1x.com/2021/06/24/RMfBSx.png" srcset="/img/loading.gif" alt="RMfBSx.png"></a></p>
<h4 id="4-2-2-3-运行时动态链接"><a href="#4-2-2-3-运行时动态链接" class="headerlink" title="4.2.2.3 运行时动态链接"></a>4.2.2.3 运行时动态链接</h4><p>采用装入时动态链接方式，虽然可将一个装入模块装入到内存的任何地方，但装入模块的结构是静态的，表现在：</p>
<ul>
<li><p><strong>进程（程序）在整个执行期间，装入模块是不改变的</strong></p>
</li>
<li><p><strong>每次运行时的装入模块是相同的</strong></p>
</li>
</ul>
<p>并且事先无法知道本次要运行哪些模块，只能将所有可能要运行的模块在装入时全部链接在一起，而实际上往往有些目标模块根本不会运行。</p>
<p>采用运行时动态链接可<strong>将某些目标模块的链接推迟到执行时才进行</strong>，即在执行过程中，若发现一个被调用模块尚未装入内存时，由OS去找到该模块，将它装入内存，并链接到调用模块上。</p>
<ul>
<li><p>主要优点：</p>
<p>凡是在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。</p>
</li>
</ul>
<p><strong>运行时动态链接是目前最常使用的链接方式。</strong></p>
<h2 id="4-3-连续分配存储管理方式"><a href="#4-3-连续分配存储管理方式" class="headerlink" title="4.3 连续分配存储管理方式"></a>4.3 连续分配存储管理方式</h2><p> 连续分配：为用户程序分配一个连续的内存空间。</p>
<p>程序空间本类就是连续的。</p>
<p>用连续的内存装入连续的程序，减少管理工作的难度。</p>
<ul>
<li><p>连续分配方式分类：</p>
<ul>
<li><p>单一连续分配</p>
<p>单用户系统在一段时间内，只有一个进程在内存，故内存分配管理十分简单，内存利用率低。<strong>内存分为两个区域，一个供操作系统使用，一个供用户使用</strong>。</p>
</li>
<li><p>分区式分配方式</p>
<p>系统把内存用户区划分为若干分区，<strong>分区大小可以相等，也可以不等</strong>。<strong>一个进程占据一个分区</strong>。这是早期用于多道程序的一种较简单的存储管理方式。它又可以分为：</p>
<ul>
<li>固定分区分配</li>
<li>动态分区分配</li>
</ul>
</li>
<li><p>动态可重定位分区分配</p>
</li>
</ul>
</li>
</ul>
<h3 id="4-3-1-单一连续分配"><a href="#4-3-1-单一连续分配" class="headerlink" title="4.3.1 单一连续分配"></a>4.3.1 单一连续分配</h3><p><strong>内存中仅驻留一道用户程序，整个用户区为一个用户独占</strong>。</p>
<p>内存分为两个区域：<strong>系统区，用户区</strong>。应用程序装入到用户区，可使用用户区全部空间。</p>
<p>最简单，适用于单用户、单任务的OS。</p>
<ul>
<li><p>优点：易于管理。</p>
<p>缺点：</p>
<p>​    对要求内存空间少的程序，造成内存浪费</p>
<p>​    <strong>程序全部装入，很少使用的程序部分也占用内存</strong></p>
<p>​    例如：DOS 2.0以下的DOS操作系统采用单一连续区域主存管理方法。</p>
</li>
</ul>
<p><a href="https://imgtu.com/i/RMT3lR"><img src="https://z3.ax1x.com/2021/06/24/RMT3lR.png" srcset="/img/loading.gif" alt="RMT3lR.png"></a></p>
<p><a href="https://imgtu.com/i/RMTb7T"><img src="https://z3.ax1x.com/2021/06/24/RMTb7T.png" srcset="/img/loading.gif" alt="RMTb7T.png"></a></p>
<h3 id="4-3-2-固定分区分配"><a href="#4-3-2-固定分区分配" class="headerlink" title="4.3.2 固定分区分配"></a>4.3.2 固定分区分配</h3><p>固定分区分配思想：将内存用户空间划分为若干个固定大小的区域，每个区域称为一个分区（region），在<strong>每个分区中只装入一道作业 ，从而支持多道程序并发设计</strong>。</p>
<p>由于这些存储区域是在系统启动时划定的，在用户作业装入及运行过程中，其<strong>区域的大小和边界是不能改变</strong>的。</p>
<ul>
<li><p>固定式分区的划分方法有两种：</p>
<ul>
<li><p>分区大小相等</p>
<p>当程序太小时，会造成内存空间的浪费 。当程序太大时，一个分区又不足以装入该程序，致使该程序无法运行。 </p>
</li>
<li><p>分区大小不等</p>
<p>可把内存区划成含有多个较小的分区、适量的中等分区及少量的大分区。 </p>
</li>
</ul>
</li>
</ul>
<p>为了实现这种固定分区的分配，系统需要建立一张<strong>分区说明表</strong>。这个分区说明表<strong>指出可用于分配的分区数以及每个区的大小、起始地址及状态</strong>。</p>
<p><a href="https://imgtu.com/i/RMH0sI"><img src="https://z3.ax1x.com/2021/06/24/RMH0sI.png" srcset="/img/loading.gif" alt="RMH0sI.png"></a></p>
<p><strong>内存分配过程？</strong></p>
<p>当有作业要装入内存时，内存分配程序检索分区说明表，从中找出一个<strong>尚未使用的满足大小要求</strong>的分区分配给该作业，然后修改分区的状态；如果找不到合适的分区就拒绝为该作业分配内存。</p>
<p><a href="https://imgtu.com/i/RMbt00"><img src="https://z3.ax1x.com/2021/06/24/RMbt00.png" srcset="/img/loading.gif" alt="RMbt00.png"></a></p>
<p><strong>内存中已分配给用户但未被利用的区域称为“内零头”（内碎片）</strong></p>
<p>固定分区分配有内零头产生。</p>
<p><a href="https://imgtu.com/i/RMqegJ"><img src="https://z3.ax1x.com/2021/06/24/RMqegJ.png" srcset="/img/loading.gif" alt="RMqegJ.png"></a></p>
<ul>
<li><p>优点：易于实现，开销小。</p>
<p>缺点：</p>
<p>​    内碎片造成浪费</p>
<p>​    分区总数固定，限制了并发执行的程序数目。</p>
<p>​    存储空间的利用率太低，现在的操作系统几乎不用它了。</p>
</li>
</ul>
<p>采用的数据结构：分区表－记录分区的大小和使用情况</p>
<h3 id="4-3-3-动态分区分配"><a href="#4-3-3-动态分区分配" class="headerlink" title="4.3.3 动态分区分配"></a>4.3.3 动态分区分配</h3><p>为了减少存储区域的内零头，进一步提高主存的利用率，使存储空间的划分更加适应不同的作业组合，设计了动态(可变)式分区方案。</p>
<p>动态分区分配是指根据进程的实际需要，动态地为之分配连续的内存空间。即<strong>分区的边界可以移动，分区的大小是可变</strong>的。</p>
<ul>
<li><p>动态分区又有两种不同选择：</p>
<ul>
<li><p>分区的数目固定大小是可变的</p>
<p>假定系统初始化时规定把存储空间划分为8个分区。在下图(a)中用问号(?)来表示它们。在系统运行一段时间后，已有192K存储空间分配给7个作业，剩下64K还未分配，如下图(b)所示。现在，又有两个作业 P和Q准备调入，它们每个需要32K存储空间。显然，我们有足够的存储空间。却没有足够数的存储区域(目前只有一个可用)。因此，只能允许一个作业(如：P)被调入，如下图(c)所示。</p>
<p><a href="https://imgtu.com/i/RMOdtf"><img src="https://z3.ax1x.com/2021/06/24/RMOdtf.png" srcset="/img/loading.gif" alt="RMOdtf.png"></a></p>
</li>
<li><p>允许分区的数目和大小都是可变的</p>
<p>第二种方案(分区数目可变)：最初，没有建立任何分区，整个可用的存储空间用一个问号来表示；之后，发生上述所说在系统运行一段时间后，已有192K存储空间分配给7个作业，剩下64K还未分配的情况，如图(b)；现在，我们在剩下的64K存储空间中，可以创建两个分区，分别装入作业P和Q，如图(c)。显然，此方案比第一个方案更灵活，内存利用率更高。</p>
<p><a href="https://imgtu.com/i/RMOHBR"><img src="https://z3.ax1x.com/2021/06/24/RMOHBR.png" srcset="/img/loading.gif" alt="RMOHBR.png"></a></p>
</li>
</ul>
</li>
<li><p>分区分配中的数据结构</p>
<ul>
<li>常用数据结构<ul>
<li>空闲分区表</li>
<li>空闲分区链</li>
</ul>
</li>
</ul>
</li>
</ul>
<p><a href="https://imgtu.com/i/RMXRrd"><img src="https://z3.ax1x.com/2021/06/24/RMXRrd.png" srcset="/img/loading.gif" alt="RMXRrd.png"></a></p>
<ul>
<li><p>分区分配算法</p>
<p>系统运行一段时间后，在整个存储空间内将出现许多大小不等的区域，有的仍被作业进程占用，有的则因作业已退出系统而成为可用于再分配的区域。现在假设有一个新的作业需调入主存，如何为其选择一个合适的区域？</p>
<ul>
<li>基于顺序搜索<ul>
<li>最佳适应算法(Best Fit)</li>
<li>最坏适应算法(Worst Fit)</li>
<li>首次适应算法(First Fit)</li>
<li>循环首次(下次)适应算法(Next Fit)</li>
</ul>
</li>
<li>基于索引搜索<ul>
<li>伙伴系统</li>
<li>快速适应算法(Quick Fit)</li>
<li>哈希算法</li>
</ul>
</li>
</ul>
<p>各个算法详解</p>
<ul>
<li><p>最佳适应算法(Best Fit:BF)</p>
<p>就是为一作业选择分区时，总是寻找其大小最接近作业所要求的存储区域。即：把作业放入这样的分区后剩下的零头最小。</p>
<p>优点：如果存储空间中具有正好是所要求大小的存储空白区，则必然被选中；如果不存在这样的空白区，也只对比要求稍大的空白区进行划分，而绝不会去划分一个更大的空白区。因此，其后遇到大作业到来时，作业要求的存储区域就比较容易得到满足。</p>
<p>缺点：在每次分配时，总是产生最小的空白区。因此，经过一段时期后，存储空间中可能留许多这样的空白区，由于其太小而无法使用。</p>
<p>为了改善这种情况，<strong>在该算法中设置一参数G，用它来确定最小分区的大小。当选择一个分区时，如果选中的空白区与要求的大小之差小于G，则不再对它划分，而把整个这个空白区分配给申请的作业。</strong></p>
<p>为了加快查找速度，应将存储空间中所有的<strong>空白区按其大小递增的顺序链接起来</strong>，组成一<strong>空白区链</strong>(Free List)。</p>
<p><a href="https://imgtu.com/i/RMjj6e"><img src="https://z3.ax1x.com/2021/06/24/RMjj6e.png" srcset="/img/loading.gif" alt="RMjj6e.png"></a></p>
<p>最佳适应算法的另一缺点是：在回收一个分区时，为了把它插入到空白区链中合适的位置上也颇为费时。所以，这种算法乍看起来是最佳的，其实则不然。</p>
</li>
<li><p>最坏适应算法(Worst Fit:WF)</p>
<p>在为作业选择存储区域时，总是寻找最大的空白区。在划分后剩下的空白区也是最大的，因而对以后的分配很可能仍然是有用的，这是该算法的一个优点。但是，由于最大的空白块总是首先被分配而进行划分，当有大的作业时，其存储空间的申请往往得不到满足，这是该算法的一个缺点。 </p>
<p>为了支持这个算法的实现，空白块应以大小递减的顺序链接起来。</p>
<p><a href="https://imgtu.com/i/RMxxII"><img src="https://z3.ax1x.com/2021/06/24/RMxxII.png" srcset="/img/loading.gif" alt="RMxxII.png"></a></p>
</li>
<li><p>首次适应算法(First Fit:FF)</p>
<p>每个<strong>空白区按其在存储空间中地址递增的顺序链在一起</strong>，即每个后继空白区的起始地址总是比前者的大。在为作业分配存储区域时，从这个空白区链的始端开始查找，选择第一个足以满足请求的空白块，而不管它究竟有多大。</p>
<p>选择的空白区被分成两部分。一部分与请求的大小相等，分配给作业；剩下的部分留在空白区链中。</p>
<p>显然，这个算法倾向于优先利用存储空间中低址部分的空白区。</p>
<p><a href="https://imgtu.com/i/RQSPt1"><img src="https://z3.ax1x.com/2021/06/24/RQSPt1.png" srcset="/img/loading.gif" alt="RQSPt1.png"></a></p>
<p>优点：算法简单，查找速度快；留在高址部分的大的空白区被划分的机会较少，因而在大作业到来时也比较容易得到满足。</p>
<p>缺点：这种算法常常利用一个大的空白区适应小作业的请求，从而留下一些较小的无法用的空白区，<strong>存储空间利用率不高</strong>；而且，由于所有的请求都是从空白区链的始端开始查找，因而这些小而无用的空白区集中在这个链的前端，相应地，一些较大空白区在链的尾端才能发现，这种情况将使<strong>找到合适空白区的速度降低</strong>。</p>
<p><strong>在低地址部分会积累大量外零头。</strong></p>
</li>
<li><p>内零头与外零头</p>
<ul>
<li><p>内零头</p>
<p>分配给用户但用户没有使用的空间</p>
<p>“多分配的空间”</p>
</li>
<li><p>外零头</p>
<p>没有分配但无法分配的空间</p>
<p>太小而无法分配，“分不出去的空间”</p>
</li>
</ul>
<p>单一连续分配有较大的内零头</p>
<p>分区分配有小于一个分区的内零头</p>
</li>
<li><p>循环首次适应算法(Next Fit:NF)</p>
<p>首次适应算法的一种变形，故也被称为带旋转指针的首次适应算法</p>
<p><strong>把存储空间中空白区构成一个循环链</strong>。<strong>每次为存储请求查找合适的分区时，总是从上次查找结束的地方开始，只要找到一个足够大的空白区，就将它划分后分配出去</strong>。</p>
<p>显然，采用这一策略后，<strong>存储空间的利用更加均衡</strong>，而不至于使小的空白区集中于存储器的一端。但是，在存储器的另一端也不可能保留大的空白块，因此，<strong>当需要获得相当大的空白区时，能满足的可能性减少</strong>了。</p>
</li>
<li><p>快速适应算法(Quick Fit:QF)</p>
<p><strong>将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表。</strong></p>
<p>这样，系统中<strong>存在多个空闲分区链表</strong>；</p>
<p>同时，在内存中设立一张管理分区类型，并记录了该类型空闲分区链表表头的索引表，该表的每一个表项记录了对应类型空闲分区链表表头的指针。</p>
<p>分配过程：<strong>根据进程的长度，寻找到能容纳它的最小空闲分区链表，并取下第一块进行分配</strong>即可。</p>
<p>优点：</p>
<ul>
<li>查找效率高。</li>
<li>该算法在进行空闲分区分配时，不会对任何分区产生分割，所以能保留大的分区，满足对大空间的需求，也<strong>不会产生内存碎片</strong>。</li>
</ul>
<p>缺点：</p>
<ul>
<li>在分区<strong>归还</strong>主存时算法复杂，系统开销较大。</li>
<li>该算法在分配空闲分区时是以进程为单位，一个分区只属于一个进程，因此在为进程所分配的一个分区中，或多或少地存在一定的浪费。空闲分区划分越细，浪费则越严重。</li>
<li>以空间换时间。</li>
</ul>
</li>
</ul>
</li>
</ul>
<p>涉及动态分区的主要操作有<strong>分配内存和回收内存</strong>。这些操作是在程序接口中通过系统调用发出的。</p>
<p><strong>1.分配内存</strong>：向操作系统提出一特定存储量的请求。通常，它并不要求这个分配的存储区域限于特定的位置，但是，这个区域必须是连续的。</p>
<p>系统利用某种分配算法，从空闲分区链(表)中找到所需大小的分区。</p>
<p>请求的分区大小为u.size</p>
<p>表中每个空闲分区的大小为m.size</p>
<p>size是事先规定的不再切割的剩余分区的大小</p>
<p><a href="https://imgtu.com/i/RQnJTx"><img src="https://z3.ax1x.com/2021/06/24/RQnJTx.png" srcset="/img/loading.gif" alt="RQnJTx.png"></a></p>
<p><strong>2.回收内存</strong>：</p>
<p>进程用于归还一个不再需用的存储区域。</p>
<p>当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链(表)中找到相应的插入点。</p>
<p>在回收一个分区时，一个回收的分区与空白区邻接的情况有四种，对这四种情况分别作如下处理：</p>
<p><a href="https://imgtu.com/i/RQnHA0"><img src="https://z3.ax1x.com/2021/06/24/RQnHA0.png" srcset="/img/loading.gif" alt="RQnHA0.png"></a></p>
<ul>
<li><p>回收区与插入点的前一个空闲分区F1相邻接。此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需<strong>修改其前一分区F1的大小</strong>。</p>
</li>
<li><p>回收区仅与下面的空白区邻接，合并后仍为空白区F2，但其<strong>起始地址和大小均需改变</strong>。用回收区的首址作为新空闲区的首址，大小为两者之和。</p>
</li>
<li><p>回收区与上、下面的空白区邻接，此时将三个分区合并，<strong>使用F1的表项和F1的首址，取消F2的表项，大小为三者之和</strong>。</p>
</li>
<li><p>回收区与上、下面的空白区均不邻接，在这种情况下，应为回收区单独<strong>建立一新表项</strong>，填写回收区的首址和大小，并<strong>根据首地址插入到空闲链中的适当位置</strong>。</p>
</li>
</ul>
<h3 id="4-3-4-伙伴系统"><a href="#4-3-4-伙伴系统" class="headerlink" title="4.3.4 伙伴系统"></a>4.3.4 伙伴系统</h3><ul>
<li><p>固定分区与动态分区方案存在的问题：</p>
<ul>
<li><strong>算法复杂，回收分区时系统开销大</strong></li>
<li>并发执行的进程数量受到限制</li>
<li>内部碎片影响内存利用率</li>
</ul>
</li>
<li><p>伙伴系统——一种折中方案</p>
</li>
<li><p>在伙伴系统中，可用内存块大小为2 <sup>k</sup>(1≤k≤m)</p>
<p>2<sup>1</sup>表示分配的最小块的尺寸</p>
<p>2<sup>m</sup>表示分配的最大块的尺寸，<strong>通常是可供分配的整个内存空间的大小</strong></p>
</li>
<li><p>对空闲区按照大小分类，相同大小的分区链接为一个双向空闲链表；最多可形成k(0 ≤k≤m)个链表。</p>
</li>
<li><p>工作流程</p>
<p>进程请求大小为n的存储空间时，</p>
<p>首先计算一个 i 值，使2<sup>i-1</sup> &lt; n ≤ 2<sup>i</sup>；</p>
<p>在空闲分区大小为2<sup>i</sup>的空闲分区链表中查找。</p>
<p>if 找到，即把该空闲分区分配给进程。</p>
<p> else 在分区大小为的空闲分区链表中寻找;</p>
<p>​                //表明长度为2<sup>i</sup>的空闲分区已经耗尽</p>
<p>if 找到大小2<sup>i+1</sup>的空闲分区</p>
<p>   把该空闲分区分为相等的两个分区（一对伙伴），其中一个用于分配，另一个加入分区大小为2<sup>i</sup> 的空闲分区链表中。</p>
<p>else 查找大小为2<sup>i+2</sup> 的空闲分区…</p>
<p><a href="https://imgtu.com/i/RQKOOJ"><img src="https://z3.ax1x.com/2021/06/24/RQKOOJ.png" srcset="/img/loading.gif" alt="RQKOOJ.png"></a></p>
<p><a href="https://imgtu.com/i/RQMuff"><img src="https://z3.ax1x.com/2021/06/24/RQMuff.png" srcset="/img/loading.gif" alt="RQMuff.png"></a></p>
</li>
</ul>
<h3 id="4-3-5-哈希算法"><a href="#4-3-5-哈希算法" class="headerlink" title="4.3.5 哈希算法"></a>4.3.5 哈希算法</h3><p>利用哈希快速查找的优点，以及空闲分区在可利用空间表中的分布规律，建立哈希函数，构造一张哈希表，以<strong>空闲分区大小为关键字</strong>，<strong>每一个表项记录了一个对应的空闲分区链表表头指针</strong>。</p>
<p>当进行空闲分区分配时，根据所需空闲分区大小，通过<strong>哈希函数计算</strong>，即得到在<strong>哈希表中的位置</strong>，从中得到相应的空闲分区链表，实现最佳分配策略。</p>
<h3 id="4-3-6-可重定向分区分配"><a href="#4-3-6-可重定向分区分配" class="headerlink" title="4.3.6 可重定向分区分配"></a>4.3.6 可重定向分区分配</h3><ul>
<li><p>紧凑</p>
<p>可变式分区分配策略是在装入作业时根据其要求量为其划定相应的区域。这种分配策略，消除了固定式分区分配造成的“内零头”，但不可避免地在存储空间中造成“外零头”，为了进一步提高存储器的利用率，必须设法<strong>减少由于外零头造成的浪费</strong>。</p>
<p> 一个最简单而直观的解决零头问题的办法是，定时地或者在内存紧张时，把存储空间中的空白区合并为一个大的连续区。</p>
<p>实现方法：<strong>将内存中的所有作业进行移动，使它们全都相邻接，可把原来分散的多个小分区合成一个大分区</strong>。这种技术称为存储器的“紧凑”。</p>
<p>把一个作业从一个存储区域移动到另一个存储区域所发生的问题，正如把一个作业装入到与它地址空间不 一致的存储空间所引起的问题一样，需要对作业中的某些地址部分和地址常数等进行调整。</p>
<p>一个较实用且可行的办法是采用动态重定位技术。<strong>当一个作业在主存中移动后，只要改变重定位寄存器中的内容即可</strong></p>
</li>
<li><p>动态重定位</p>
<p>在动态运行时装入的方式中，作业装入内存后的所有地址都仍然是相对地址，将相对地址转换为物理地址的工作，被推迟到程序指令要真正执行时进行。</p>
<p>程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。</p>
<p>动态重定位机制需要硬件的支持， 即须在系统中增设一个重定位寄存器，用它来存放程序(数据)在内存中的起始地址。</p>
<p><a href="https://imgtu.com/i/RQ1PpV"><img src="https://z3.ax1x.com/2021/06/24/RQ1PpV.png" srcset="/img/loading.gif" alt="RQ1PpV.png"></a></p>
</li>
<li><p>动态重定位分区分配</p>
</li>
</ul>
<p><a href="https://imgtu.com/i/RQ1Q1K"><img src="https://z3.ax1x.com/2021/06/24/RQ1Q1K.png" srcset="/img/loading.gif" alt="RQ1Q1K.png"></a></p>
<h2 id="4-4-基于分页存储管理方式"><a href="#4-4-基于分页存储管理方式" class="headerlink" title="4.4 基于分页存储管理方式"></a>4.4 基于分页存储管理方式</h2><ul>
<li><p><strong>离散分配方式</strong>的引入</p>
<p><strong>连续分配方式会产生内/外零头</strong></p>
<p><strong>为解决零头问题又要进行紧凑等高开销活动</strong></p>
<p>前面介绍的分区存储管理，一般都要求把一个作业的地址空间装入到连续的存储区域内。因此，在动态分区的存储空间中，常常由于存在着一些不足以装入任何作业的小的分区而浪费掉部分存储资源，这就是所谓存储器的零头问题。</p>
<p>尽管采用“紧凑”技术可以解决这个问题，但要为移动大量信息花去不少处理机时间，代价较高。</p>
<p>如果我们能取消对其存储区域的连续性要求，必然会进一步提高主存空间的利用率，又无需为移动信息付出代价。</p>
</li>
<li><p>什么是离散分配</p>
<p>程序在内存中不一定连续存放</p>
</li>
<li><p>根据离散时的基本单位不同，可分为三种：</p>
<ul>
<li>分页存储管理、</li>
<li>分段存储管理</li>
<li>段页式存储管理</li>
</ul>
</li>
</ul>
<h3 id="4-4-1-分页存储管理基本思想"><a href="#4-4-1-分页存储管理基本思想" class="headerlink" title="4.4.1 分页存储管理基本思想"></a>4.4.1 分页存储管理基本思想</h3><ul>
<li><p>离散的基础</p>
<p><strong>分页(Pages)：将程序地址空间分页</strong></p>
<p><strong>分块(Frames)：将内存空间分块</strong></p>
</li>
<li><p>离散分配的体现</p>
<p>内存一块可以装入程序一页</p>
<p><strong>连续的多个页不一定装入连续的多个块中。</strong></p>
<p>注意：系统中页块的大小是不变的。</p>
</li>
<li><p>离散分配的优点</p>
<p>没有外零头：不受连续空间限制，每块都能分出去</p>
<p>仅有小于一个页面的内零头：程序大小一般不是页大小的整数倍</p>
<p><strong>由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”或称为“内零头”。</strong></p>
<p><a href="https://imgtu.com/i/RQGkX8"><img src="https://z3.ax1x.com/2021/06/24/RQGkX8.png" srcset="/img/loading.gif" alt="RQGkX8.png"></a></p>
</li>
<li><p>页面与物理块</p>
<p>页面或页(Page)：<strong>把每个进程的逻辑地址空间分成一些大小相等的片</strong>。</p>
<p>物理块或页框(Page Frame)：<strong>内存空间也分成与页相同大小的若干存储块。在为进程分配存储空间时，总是以页框为单位。</strong></p>
<p>例如：一个作业的地址空间有m页。那么，只要分配给它m个页框，每一页分别装入一个页框内即可。这里，并不要求这些页框是连续的。</p>
<p>​    说明：</p>
<p>​    ⑴从0开始编制页号，页内地址是相对于0编址；</p>
<p>​    ⑵在<strong>进程调度时，必须把它的所有页一次装入到主存的页框内</strong>；如果当时页框数不足，则该进程必须等待，系统再调度另外的进程。（<strong>纯分页方式</strong>）</p>
</li>
<li><p>页面大小的选择</p>
<p><strong>页面大小由机器的地址结构决定。某一机器只能采用一种大小的页面。</strong></p>
<ul>
<li><p>小页面：优点是可减少碎片，能提高内存的利用率。缺点是页表过长，占用较多的内存空间。且以页为单位进行换进、换出时效率低。</p>
</li>
<li><p>大页面：优点是页表小，换进换出时效率高。但页内碎片相应较大。</p>
</li>
</ul>
<p>页面的大小通常在1KB~8KB之间</p>
</li>
<li><p>实现分页存储管理的<strong>数据结构</strong></p>
<ul>
<li><p>页表：<strong>每个进程对应1个页表</strong>，描述该进程的各页面在内存中对应的物理块号。</p>
<ul>
<li>页表中包括页号、物理块号（<strong>还可有存取控制字段，对存储块中的内容进行保护</strong>）。</li>
<li>注意：全部页表集中<strong>存放在主存的系统专用区</strong>中，<strong>只有系统有权访问页表</strong>，保证安全。</li>
</ul>
</li>
<li><p>作业表：<strong>整个系统只有1张</strong>，记录作业的页表情况，包含进程号、页表长度、页表始址等信息。</p>
</li>
<li><p>空闲块表：<strong>整个系统只有1张</strong>，记录主存当前空闲块。</p>
</li>
</ul>
</li>
</ul>
<p><a href="https://imgtu.com/i/RQYgSI"><img src="https://z3.ax1x.com/2021/06/24/RQYgSI.png" srcset="/img/loading.gif" alt="RQYgSI.png"></a></p>
<p><a href="https://imgtu.com/i/RQtPpR"><img src="https://z3.ax1x.com/2021/06/24/RQtPpR.png" srcset="/img/loading.gif" alt="RQtPpR.png"></a></p>
<ul>
<li><p>例如：</p>
<p>假设内存能提供16个空闲页框，进程P1被分割成4个页面，装入内存中的0号至3号页框。进程P2被分割成3个页面，装入4号至6号页框。进程P3被装入7号至12号页框，如图(a)所示。</p>
<p>此时，进程P4请求分配5个页框大小的存储空间，但内存只有3个空闲页框。于是，将暂时不运行的P2交换出内存，如图(b)所示。</p>
<p>然后，再将P4装入4、5、6、13、14号页框，如图(c)所示。</p>
<p><a href="https://imgtu.com/i/RQtbUe"><img src="https://z3.ax1x.com/2021/06/24/RQtbUe.png" srcset="/img/loading.gif" alt="RQtbUe.png"></a></p>
<p><a href="https://imgtu.com/i/RQNPUg"><img src="https://z3.ax1x.com/2021/06/24/RQNPUg.png" srcset="/img/loading.gif" alt="RQNPUg.png"></a></p>
</li>
<li><p>地址结构</p>
<p>地址空间为程序限定的空间。</p>
<p>物理空间为内存限定空间。</p>
<p><strong>在页式管理系统中将地址空间分成大小相同页面。将内存空间分成与页面相同大小的存储块。</strong></p>
<p><a href="https://imgtu.com/i/RQNtr6"><img src="https://z3.ax1x.com/2021/06/24/RQNtr6.png" srcset="/img/loading.gif" alt="RQNtr6.png"></a></p>
</li>
<li><p>分页存储管理的逻辑地址表示</p>
<p><a href="https://imgtu.com/i/RQNHs0"><img src="https://z3.ax1x.com/2021/06/24/RQNHs0.png" srcset="/img/loading.gif" alt="RQNHs0.png"></a></p>
</li>
<li><p>例题：</p>
<p><a href="https://imgtu.com/i/RQauh4"><img src="https://z3.ax1x.com/2021/06/24/RQauh4.png" srcset="/img/loading.gif" alt="RQauh4.png"></a></p>
<p>计算指导：把1K换成8进制进行计算即可！</p>
</li>
</ul>
<h3 id="4-4-2-地址变换机构"><a href="#4-4-2-地址变换机构" class="headerlink" title="4.4.2 地址变换机构"></a>4.4.2 地址变换机构</h3><ul>
<li><p>地址变换机构的功能是将用户的逻辑地址转变为内存中的物理地址。</p>
<p>逻辑地址由<strong>页号和页内位移量</strong>组成。</p>
<p>页的大小和内存物理块的大小是相同的，所以页内位移量即为物理块内位移量。</p>
<p><strong>关键是页号到物理块号的转换，由页表完成。</strong></p>
<h4 id="基本的地址变换机构"><a href="#基本的地址变换机构" class="headerlink" title="基本的地址变换机构"></a>基本的地址变换机构</h4><ul>
<li><p>使用寄存器存放页表</p>
<ul>
<li>速度快，成本高。特别对于大的系统，页表很长，不可能都用寄存器实现。</li>
</ul>
</li>
<li><p><strong>一般系统，将页表存放在内存中。</strong></p>
<ul>
<li><p>设置一个<strong>页表寄存器(PTR)**，</strong>记录当前运行的进程的页表在内存中的起始地址和页表长度<strong>。(**平时存放于PCB-进程控制块中，要运行时，才装入PTR中</strong>)。</p>
<p>当进程真正投入运行时，从进程PCB中读出页表的始址和页表长度，并将这两个数据装入PTR中，以后地址转换时直接从PTR中获得页表的起始地址。</p>
</li>
</ul>
</li>
</ul>
</li>
<li><p>分页系统中的地址变换过程如下：</p>
<p>（1）根据逻辑地址,计算出页号和页内偏移量；</p>
<p>（2）从PTR中得到页表首址，然后检索页表，查找指定页面对应的页框号；</p>
<p>（3）用页框号乘以页面大小获得其对应的起始地址，并将其送入<strong>物理地址的高端</strong>。</p>
<p>（4）将<strong>页内偏移量送入物理地址低端</strong>，形成完整的物理地址。</p>
</li>
</ul>
<p><a href="https://imgtu.com/i/RQdQIS"><img src="https://z3.ax1x.com/2021/06/24/RQdQIS.png" srcset="/img/loading.gif" alt="RQdQIS.png"></a></p>
<ul>
<li><p>例题1：</p>
<p><a href="https://imgtu.com/i/RQdaZV"><img src="https://z3.ax1x.com/2021/06/24/RQdaZV.png" srcset="/img/loading.gif" alt="RQdaZV.png"></a></p>
</li>
</ul>
<p><a href="https://imgtu.com/i/RQdLeP"><img src="https://z3.ax1x.com/2021/06/24/RQdLeP.png" srcset="/img/loading.gif" alt="RQdLeP.png"></a><br><a href="https://imgtu.com/i/RQdbLt"><img src="https://z3.ax1x.com/2021/06/24/RQdbLt.png" srcset="/img/loading.gif" alt="RQdbLt.png"></a></p>
<p><strong>千万小心！！！物理块号和页表中的页号都是从0开始！！！</strong></p>
<ul>
<li><p>例题2：</p>
<p><a href="https://imgtu.com/i/RQwPLq"><img src="https://z3.ax1x.com/2021/06/24/RQwPLq.png" srcset="/img/loading.gif" alt="RQwPLq.png"></a></p>
<p><a href="https://imgtu.com/i/RQwOXR"><img src="https://z3.ax1x.com/2021/06/24/RQwOXR.png" srcset="/img/loading.gif" alt="RQwOXR.png"></a></p>
</li>
<li><p>例题3：</p>
<p><a href="https://imgtu.com/i/RQ0i1H"><img src="https://z3.ax1x.com/2021/06/24/RQ0i1H.png" srcset="/img/loading.gif" alt="RQ0i1H.png"></a></p>
</li>
</ul>
<h4 id="具有快表的地址变换机构"><a href="#具有快表的地址变换机构" class="headerlink" title="具有快表的地址变换机构"></a>具有快表的地址变换机构</h4><ul>
<li><p>分页系统中处理机每次存取指令或数据至少需要访问两次物理内存</p>
<ul>
<li>第一次访问页表，以得到物理地址</li>
<li>第二次访问物理地址，以得到数据。</li>
</ul>
</li>
<li><p>存取速度几乎降低了一倍，代价太高</p>
</li>
<li><p>为了提高地址变换速度，为进程页表设置一个专用的高速缓冲存储器，称为快表TLB(Translation Lookaside Buffer)，或联想存储器（Associative Memory）。</p>
</li>
<li><p>工作原理</p>
<p>类似于系统中的数据高速缓存(cache)，其中<strong>专门保存当前进程最近访问过的一组页表项</strong>。</p>
</li>
<li><p>进程最近访问过的页面在不久的将来还可能被访问。</p>
</li>
<li><p>工作流程</p>
<ul>
<li><p>根据逻辑地址中的页号，查找快表中是否存在对应的页表项。</p>
</li>
<li><p>若快表中存在该表项，称为<strong>命中</strong>（hit），取出其中的页框号，加上页内偏移量，计算出物理地址。</p>
</li>
<li><p>若快表中不存在该页表项，称为<strong>命中失败</strong>，则再查找页表，找到逻辑地址中指定页号对应的页框号。同时，更新快表，将该表项插入快表中。并计算物理地址.</p>
</li>
</ul>
</li>
</ul>
<p><a href="https://imgtu.com/i/RQBwIf"><img src="https://z3.ax1x.com/2021/06/24/RQBwIf.png" srcset="/img/loading.gif" alt="RQBwIf.png"></a></p>
<h3 id="4-4-3-访问内存的有效时间EAT"><a href="#4-4-3-访问内存的有效时间EAT" class="headerlink" title="4.4.3 访问内存的有效时间EAT"></a>4.4.3 访问内存的有效时间EAT</h3><ul>
<li><p>定义：<strong>从进程发出指定逻辑地址的访问请求，经过地址变换，再到内存中找到对应的物理单元并取出数据，所花费的总时间。</strong></p>
<p>因成本关系，联想存储器不是很大，通常只能存放16~512个页表项。这对中小作业，已有可能把全部页表放在其中；但对大型作业，只能放一部分。</p>
</li>
<li><p>如检索快表时间为20ns，访问内存为100 ns。</p>
<p>若能在快表中检索到CPU给出的页号，则CPU存取一个数据共需120 ns</p>
<p>否则，需要220ns的时间。</p>
</li>
<li><p>当访问联想存储器时的命中率分别为0%，50%，80%，90%，98%时，其有效访问时间如下表所示：</p>
<p><a href="https://imgtu.com/i/RQDMOs"><img src="https://z3.ax1x.com/2021/06/24/RQDMOs.png" srcset="/img/loading.gif" alt="RQDMOs.png"></a></p>
</li>
</ul>
<p><a href="https://imgtu.com/i/RQD6fO"><img src="https://z3.ax1x.com/2021/06/24/RQD6fO.png" srcset="/img/loading.gif" alt="RQD6fO.png"></a><br><a href="https://imgtu.com/i/RQDytK"><img src="https://z3.ax1x.com/2021/06/24/RQDytK.png" srcset="/img/loading.gif" alt="RQDytK.png"></a></p>
<h3 id="4-4-4-两级和多级页表"><a href="#4-4-4-两级和多级页表" class="headerlink" title="4.4.4 两级和多级页表"></a>4.4.4 两级和多级页表</h3><ul>
<li><p>问题</p>
<p>32位逻辑地址空间，假设页面大小为4KB（2<sup>12</sup>），则4GB（2<sup>32</sup>）的逻辑地址空间将被划分成220个页面。</p>
<p> 若采用一级页表，则该表将包含1M（2<sup>20</sup>）个页表项。若按字节寻址，一个页表项占4B，则一级页表需要占用4MB（2<sup>22</sup>）内存空间。<strong>不可能将4MB的页表保存在一个连续区中</strong>。</p>
<p>那么，如何处理<strong>大页表的存储与检索</strong>呢？</p>
</li>
<li><p>可以采用这样两个方法来解决这一问题：</p>
<p>① 采用离散分配方式来解决难以找到一块连续的大内存空间的问题，（即<strong>引入两级页表</strong>）；</p>
<p>② <strong>只将当前需要的部分页表项调入内存</strong>， 其余的页表项仍驻留在磁盘上，需要时再调入。</p>
</li>
<li><p>对于要求连续的内存空间来存放页表的问题：</p>
<p>可将页表进行分页，并离散地将各个页面分别存放在不同的物理块中，</p>
<p>同样也要<strong>为离散分配的页表再建立一张页表，称为外层页表</strong>(Outer Page Table)，<strong>在每个页表项中记录了页表分页的物理块号</strong>。</p>
</li>
</ul>
<p><a href="https://imgtu.com/i/RQrybn"><img src="https://z3.ax1x.com/2021/06/24/RQrybn.png" srcset="/img/loading.gif" alt="RQrybn.png"></a></p>
<p><a href="https://imgtu.com/i/RQsXoq"><img src="https://z3.ax1x.com/2021/06/24/RQsXoq.png" srcset="/img/loading.gif" alt="RQsXoq.png"></a><br><a href="https://imgtu.com/i/RQsOwn"><img src="https://z3.ax1x.com/2021/06/24/RQsOwn.png" srcset="/img/loading.gif" alt="RQsOwn.png"></a></p>
<p>地址变换机构中增设<strong>外层页表寄存器</strong>，用于存放外层页表的始址。</p>
<p>利用逻辑地址中的外层页号，作为外层页表的索引，从中找到指定页表分页的始址，再利用指定页表分页的索引，找到指定的页表项，即该页在内存的物理块号。</p>
<p>用该块号和页内地址即可构成访问的内存物理地址。 </p>
<h4 id="多级页表"><a href="#多级页表" class="headerlink" title="多级页表"></a>多级页表</h4><p>对于64位机器，采用两级页表是否合适？</p>
<p><strong>注意：4B为一个页表项大小！！！</strong></p>
<p><a href="https://imgtu.com/i/RQy3TI"><img src="https://z3.ax1x.com/2021/06/24/RQy3TI.png" srcset="/img/loading.gif" alt="RQy3TI.png"></a></p>
<p>(2^52^<em>4B)/2^12^=2^42^  个页表分页      2^42^\</em>4B=16KGB 外层页表大小</p>
<p>[<img src="https://z3.ax1x.com/2021/06/24/RQWnpt.png" srcset="/img/loading.gif" alt="RQWnpt.png"></p>
<p><a href="https://imgtu.com/i/RQWnpt"></a></p>
<h3 id="4-4-5-反置页表Inverted-Page-Table（IPT）"><a href="#4-4-5-反置页表Inverted-Page-Table（IPT）" class="headerlink" title="4.4.5 反置页表Inverted Page Table（IPT）"></a>4.4.5 反置页表Inverted Page Table（IPT）</h3><ul>
<li><p>大地址空间问题</p>
<ul>
<li>对于大地址空间(64-bits)系统，多级页表变得繁琐。</li>
<li>如：5级页表</li>
<li>逻辑(虚拟)地址空间增长速度快于物理地址空间。</li>
</ul>
</li>
<li><p>反置页表的思路</p>
<ul>
<li>不让页表与逻辑地址空间大小相对应</li>
<li>让页表和物理地址空间的大小相对应</li>
</ul>
</li>
<li><p>IPT主要解决问题</p>
<p>逻辑空间越来越大，页表占用内存也越来越大，为解决大页表问题占内存多现象，减少内存开销，避免一个进程一个页表。</p>
</li>
<li><p>IPT思想：</p>
<ul>
<li><p>IPT是为主存中的每一个物理块建立一个页表项并按照块号排序。</p>
</li>
<li><p>该表每个表项包含正在访问该物理块的进程标识、页号及特征位,<strong>用来完成主存物理块到访问进程的页号的转换</strong>。</p>
</li>
</ul>
</li>
</ul>
<p><a href="https://imgtu.com/i/RQf02t"><img src="https://z3.ax1x.com/2021/06/24/RQf02t.png" srcset="/img/loading.gif" alt="RQf02t.png"></a></p>
<ul>
<li><p><strong>Hash表检索</strong></p>
</li>
<li><p>IPT只包含已经调入内存的页面，不包含尚未调入内存的页面。</p>
</li>
<li><p>反置页表地址转换过程如下：</p>
<p>给出进程标识和页号,用它们去比较IPT,若整个反置页表中未能找到匹配的页表项,说明该页不在主存，产生<strong>请求调页中断</strong>,请求操作系统调入。</p>
<p>否则，该表项的序号便是物理块号,块号加上位移,便形成物理地址。</p>
<p><a href="https://imgtu.com/i/RQhNLT"><img src="https://z3.ax1x.com/2021/06/24/RQhNLT.png" srcset="/img/loading.gif" alt="RQhNLT.png"></a><br><a href="https://imgtu.com/i/RQhtyV"><img src="https://z3.ax1x.com/2021/06/24/RQhtyV.png" srcset="/img/loading.gif" alt="RQhtyV.png"></a></p>
</li>
</ul>
<h3 id="4-4-6-对换（Swapping）"><a href="#4-4-6-对换（Swapping）" class="headerlink" title="4.4.6 对换（Swapping）"></a>4.4.6 对换（Swapping）</h3><ul>
<li><p>对换：<strong>把内存中暂不能运行的进程或暂时不用和程序和数据，换到外存上，以腾出足够的内存空间，把已具备运行条件的进程，或进程所需要的程序和数据，换入内存。</strong></p>
<p>对换是<strong>系统行为</strong>，是提高内存的利用率的有效措施。</p>
<p>常用于<strong>多道程序系统或小型分时系统</strong>中，<strong>与分区存储管理配合使用</strong>。</p>
<p>实现：可在系统中设一对换进程，以执行换进内存、换出至外存操作。</p>
<p>对换技术，最早用在分时系统UNIX中。</p>
<p><strong>在任何时刻，在该系统的主存中只保存一个完整的用户作业</strong>，当其运行一段时间后，或由于分配给它的时间片已用完，或由于需要其它资源而等待，系统就把它交换到辅存，同时把另一个作业调入主存让其运行。这样，可以在存储容量不大的小型机上实现分时系统。Microsoft公司的 Windows OS也采用这种对换技术。</p>
<ul>
<li><p>分类：</p>
<ul>
<li><p>“整体对换”（进程对换）：</p>
<p>  <strong>对换以整个进程为单位</strong>，用于<strong>分时系统</strong>，以解决内存紧张的问题。</p>
</li>
<li><p>“页面对换/分段对换”：</p>
<p> <strong>对换以“页”或“段”为单位进行“部分对换”</strong>，<strong>该方法是实现请求分页及请求分段存储器的基础，支持虚存系统</strong>。</p>
</li>
</ul>
</li>
</ul>
</li>
<li><p>为实现对换，系统需要三方面的功能：</p>
<ul>
<li>对换空间管理</li>
<li>进程的换入</li>
<li>进程的换出</li>
</ul>
</li>
</ul>
<p>一、对换空间管理</p>
<ul>
<li><p><strong>外存被分为两部分，文件区和对换区</strong></p>
<p>Windows常用的分区格式有三种，分别是FAT16、FAT32、NTFS格式。在Linux操作系统里有Ext2、Ext3、Linux swap和VFAT四种格式。</p>
<ul>
<li><p>文件区用于存放文件，对它的管理应重在如何<strong>提高存储空间的利用率</strong>。所以对它采取<strong>离散分配方式</strong>。</p>
<p>即：一个文件可根据当前外存的使用情况，被分成多块，分别存储到不邻接的多个存储区域中，用指针相连。</p>
</li>
<li><p>对换区存放从内存换出的进程，它们在外存的存放时间较短，换入、换出频繁。对对换区的管理应重在<strong>提高进程的换入换出速度</strong>。因此采用<strong>连续分配方式</strong>。</p>
<p>即：把一个换出的进程存放到一个连续的存储空间中。</p>
</li>
</ul>
</li>
<li><p>为了能对对换区中的空闲盘块进行管理，在系统中应配置相应的数据结构，以记录外存的使用情况。</p>
<p><strong>空闲分区表或空闲分区链</strong>。在空闲分区表中的每个表目应包含两项，即<strong>对换分区首址和对换区长度</strong>，它们的<strong>基本单位都是盘块</strong>。（盘块的大小和操作系统的具体文件系统有关系！比如FAT32的盘块大小为4KB）</p>
</li>
<li><p>对换区的分配，是采用连续分配方式。因而对对换区空间的分配与回收，与动态分区方式时内存的分配与回收方法雷同。</p>
<p>分配算法可以是<strong>首次适应算法、循环首次适应算法和最佳适应算法</strong>。</p>
<p>回收操作也可分为四种情况。</p>
</li>
</ul>
<p>二、进程换入与换出(由对换进程完成)</p>
<ul>
<li><p>换出 swap out</p>
<p>选择：首先选择阻塞或睡眠状态的进程，若有多个，按<strong>优先级</strong>由低到高进行选择。若没有此状态进程，则选择就绪状态的，仍然按优先级由低到高进行选择。</p>
<p>为避免某进程被频繁的换入换出，还应考虑进程在内存中的驻留时间，<strong>优先选择驻留时间长的进程</strong>。</p>
</li>
<li><p>换入 swap in</p>
<p>①从 PCB集合中查找“就绪且换出”的进程，有多个，则<strong>选择换出时间最长</strong>的。</p>
<p>②<strong>根据进程大小申请内存，成功则读入，否则要先执行换出，再换入</strong>。</p>
<p>③若还有可换入进程，则转向①。<strong>直至无“就绪且换出”进程或无法获得足够内存空间为止</strong>。</p>
<h2 id="4-5-基本分段式存储管理"><a href="#4-5-基本分段式存储管理" class="headerlink" title="4.5 基本分段式存储管理"></a>4.5 基本分段式存储管理</h2></li>
</ul>
<p>4.5.1 分段式存储管理方式的引入<br>4.5.2 分段式存储管理的基本原理<br>4.5.3 段的共享和保护<br>4.5.4 段页式存储管理</p>
<p>引言：程序员眼中的程序 模块化程序设计的分段结构</p>
<p>模块化程序设计的分段结构</p>
<h3 id="4-5-1-分段存储管理方式的引入"><a href="#4-5-1-分段存储管理方式的引入" class="headerlink" title="4.5.1 分段存储管理方式的引入"></a>4.5.1 分段存储管理方式的引入</h3><ul>
<li><p>分段存储管理更加符合用户和程序员的如下需求：</p>
<ul>
<li><p>方便编程</p>
</li>
<li><p>信息共享</p>
<ul>
<li><p>一般实现程序和数据共享时都是以信息的<strong>逻辑单位</strong>（过程、函数或文件）为基础的。</p>
</li>
<li><p>在分页系统中的每一页都只是存放信息的物理单位，其本身并无完整意义，因而不便于实现信息共享。</p>
</li>
<li><p><strong>段是信息的逻辑单位</strong>，可以为共享过程建立一个独立的段，更便于实现程序和数据的共享。</p>
</li>
</ul>
</li>
<li><p>信息保护</p>
<ul>
<li>对内存中的信息的保护，同样也是对信息的逻辑单位进行保护。</li>
<li>采用分段存储管理，对实现保护，将是更有效和方便。</li>
</ul>
</li>
<li><p>动态链接</p>
<ul>
<li>程序运行时，先将主程序所对应的目标程序装入内存并启动运行，当运行过程中又需要调用某段时，才将该段调入内存并进行链接。</li>
</ul>
</li>
<li><p>动态增长</p>
<ul>
<li>在实际使用中，往往有些段，特别是数据段会随着程序的运行不断增大，而这种增长事先并不知晓会增长到多大，采用其它存储管理方式是难以应付的，而分段存储管理却能较好的解决这一问题。 </li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 id="4-5-2-分段管理系统的基本原理"><a href="#4-5-2-分段管理系统的基本原理" class="headerlink" title="4.5.2 分段管理系统的基本原理"></a>4.5.2 分段管理系统的基本原理</h3><p><strong>一、分段</strong></p>
<ul>
<li>作业地址空间<strong>按逻辑信息的完整性</strong>被划分为若干个段；</li>
<li>每段有段名（或段号），每段从0开始编址；</li>
<li>段内的地址空间是连续的。</li>
<li>许多编译程序支持分段方式，<strong>自动根据源程序的情况产生若干个段</strong>。</li>
</ul>
<p>在分段管理系统中，对所有地址空间的访问均要求两个成分：</p>
<ul>
<li>段的名字</li>
<li>段内地址</li>
</ul>
<p>例如，可按下述调用：</p>
<p>CALL [X]|&lt;Y&gt;    转移到子程序X中的入口点Y</p>
<p>LOAD 1, [A]|&lt;D&gt;  将数组A的D单元的值读入寄存器1</p>
<p>STORE 1,[B]|&lt;C&gt;将寄存器1的内容存入分段B的C单元中</p>
<p>这些符号程序经汇编和装配后，指令和数据的单元地址均由两部分构成：一是表示段名的段号S；一是位移量W，即段内地址。所以，在分段系统中的地址结构有如下形式：</p>
<p><a href="https://imgtu.com/i/Rl2AOS"><img src="https://z3.ax1x.com/2021/06/25/Rl2AOS.png" srcset="/img/loading.gif" alt="Rl2AOS.png"></a></p>
<p>一旦段号字段和位移量字段的长度确定后，一个作业地址空间中允许的最多段数及段的长度也就限定了。</p>
<p><strong>分段管理</strong>：<strong>就是管理由若干分段组成的作业，且按分段来进行存储分配</strong></p>
<p>实现分段管理的关键在于，如何保证分(二维)地址空间中的一个作业在线性(一维)的存储空间中正确运行。</p>
<p>也就是说，如何把分段地址结构变换成线性的地址结构，和分页管理一样，可采用<strong>动态重定位技术</strong>，即通过地址变换机构来实现。</p>
<p><strong>二、段表</strong></p>
<ul>
<li>为每个分段分配一个连续的分区，而进程中的各个段可以离散地移入内存中不同的分区中。</li>
<li>应像分页系统那样，在系统中为每个进程建立一张段映射表，简称“段表”。每个段在表中占有一个表项，其中记录了该段在内存中的起始地址（又称为“基址”）和段的长度。</li>
<li>通常将段表放在内存中，执行中的进程可通过查找段表找到每个段所对应的内存区。</li>
</ul>
<p><strong>作用：实现从逻辑段到物理内存区的映射。</strong></p>
<p><a href="https://imgtu.com/i/Rl2qts"><img src="https://z3.ax1x.com/2021/06/25/Rl2qts.png" srcset="/img/loading.gif" alt="Rl2qts.png"></a></p>
<p> 每个表项（段描述子）至少有三个数据项：段长、主存起始地址和存取控制。</p>
<p>段长指明它的大小；</p>
<p>主存起始地址指出该段在主存中的位置；</p>
<p>存取控制说明对该段访问的限制(R＝1，允许读；W=1，允许写；X=1,允许执行) 。</p>
<p><a href="https://imgtu.com/i/RlRnBD"><img src="https://z3.ax1x.com/2021/06/25/RlRnBD.png" srcset="/img/loading.gif" alt="RlRnBD.png"></a><br><a href="https://imgtu.com/i/RlRmnO"><img src="https://z3.ax1x.com/2021/06/25/RlRmnO.png" srcset="/img/loading.gif" alt="RlRmnO.png"></a></p>
<p>问：若段表放在内存中，每访问一个数据需要访问内存几次？  2次</p>
<p>可设置联想存储器（快表），以提高访问速度。</p>
<ul>
<li>优点：<ul>
<li>没有内碎片，外碎片可以通过内存紧凑来消除。便于改变进程占用空间的大小。</li>
</ul>
</li>
<li>缺点<ul>
<li>进程全部装入内存</li>
</ul>
</li>
</ul>
<h3 id="4-5-3-段的共享和保护"><a href="#4-5-3-段的共享和保护" class="headerlink" title="4.5.3 段的共享和保护"></a>4.5.3 段的共享和保护</h3><h3 id="4-5-4-段页式存储管理"><a href="#4-5-4-段页式存储管理" class="headerlink" title="4.5.4 段页式存储管理"></a>4.5.4 段页式存储管理</h3><h2 id="4-6-虚拟存储器的基本概念"><a href="#4-6-虚拟存储器的基本概念" class="headerlink" title="4.6 虚拟存储器的基本概念"></a>4.6 虚拟存储器的基本概念</h2><h3 id="4-6-1-虚拟存储器的引入"><a href="#4-6-1-虚拟存储器的引入" class="headerlink" title="4.6.1 虚拟存储器的引入"></a>4.6.1 虚拟存储器的引入</h3><h3 id="4-6-2-局部性原理"><a href="#4-6-2-局部性原理" class="headerlink" title="4.6.2 局部性原理"></a>4.6.2 局部性原理</h3>
            </div>
            <hr>
            <div>
              <div class="post-metas mb-3">
                
                
                  <div class="post-meta">
                    <i class="iconfont icon-tags"></i>
                    
                      <a class="hover-with-bg" href="/tags/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F3-8%E7%AB%A0/">操作系统3-8章</a>
                    
                  </div>
                
              </div>
              
                <p class="note note-warning">
                  
                    本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-sa/4.0/deed.zh" rel="nofollow noopener">CC BY-SA 4.0 协议</a> ，转载请注明出处！
                  
                </p>
              
              
                <div class="post-prevnext">
                  <article class="post-prev col-6">
                    
                    
                      <a href="/2021/05/05/%E5%89%8D%E7%AB%AF%E5%AD%A6%E4%B9%A012/">
                        <i class="iconfont icon-arrowleft"></i>
                        <span class="hidden-mobile">CSS属性-动画</span>
                        <span class="visible-mobile">上一篇</span>
                      </a>
                    
                  </article>
                  <article class="post-next col-6">
                    
                    
                      <a href="/2021/04/17/%E8%BF%9B%E7%A8%8B%E5%90%8C%E6%AD%A5/">
                        <span class="hidden-mobile">进程</span>
                        <span class="visible-mobile">下一篇</span>
                        <i class="iconfont icon-arrowright"></i>
                      </a>
                    
                  </article>
                </div>
              
            </div>

            
          </article>
        </div>
      </div>
    </div>
    
      <div class="d-none d-lg-block col-lg-2 toc-container" id="toc-ctn">
        <div id="toc">
  <p class="toc-header"><i class="iconfont icon-list"></i>&nbsp;目录</p>
  <div class="toc-body" id="toc-body"></div>
</div>

      </div>
    
  </div>
</div>

<!-- Custom -->

  <div class="col-lg-7 mx-auto nopadding-x-md">
    <div class="container custom post-custom mx-auto">
      <img src="https://octodex.github.com/images/jetpacktocat.png" srcset="/img/loading.gif" class="rounded mx-auto d-block mt-5" style="width:150px; height:150px;">
    </div>
  </div>


    

    
      <a id="scroll-top-button" href="#" role="button">
        <i class="iconfont icon-arrowup" aria-hidden="true"></i>
      </a>
    

    
      <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">搜索</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v"
                 for="local-search-input">关键词</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>
    

    
  </main>

  <footer class="text-center mt-5 py-3">
  <div class="footer-content">
     <a href="https://hexo.io" target="_blank" rel="nofollow noopener"><span>Hexo</span></a> <i class="iconfont icon-love"></i> <a href="https://github.com/fluid-dev/hexo-theme-fluid" target="_blank" rel="nofollow noopener"><span>Fluid</span></a> 
  </div>
  

  
  <!-- 备案信息 -->
  <div class="beian">
    <span>
      <a href="http://beian.miit.gov.cn/" target="_blank" rel="nofollow noopener">
        京ICP证123456号
      </a>
    </span>
    
      
        <span>
          <a
            href="http://www.beian.gov.cn/portal/registerSystemInfo?recordcode=12345678"
            rel="nofollow noopener"
            class="beian-police"
            target="_blank"
          >
            
              <span style="visibility: hidden; width: 0">|</span>
              <img src="/img/police_beian.png" srcset="/img/loading.gif" alt="police-icon"/>
            
            <span>京公网安备12345678号</span>
          </a>
        </span>
      
    
  </div>


  
</footer>

<!-- SCRIPTS -->

  <script  src="https://cdn.jsdelivr.net/npm/nprogress@0.2.0/nprogress.min.js" ></script>
  <link  rel="stylesheet" href="https://cdn.jsdelivr.net/npm/nprogress@0.2.0/nprogress.min.css" />

  <script>
    NProgress.configure({"showSpinner":false,"trickleSpeed":100})
    NProgress.start()
    window.addEventListener('load', function() {
      NProgress.done();
    })
  </script>


<script  src="https://cdn.jsdelivr.net/npm/jquery@3.5.1/dist/jquery.min.js" ></script>
<script  src="https://cdn.jsdelivr.net/npm/bootstrap@4.5.3/dist/js/bootstrap.min.js" ></script>
<script  src="/js/debouncer.js" ></script>
<script  src="/js/events.js" ></script>
<script  src="/js/plugins.js" ></script>

<!-- Plugins -->


  
    <script  src="/js/lazyload.js" ></script>
  



  



  <script  src="https://cdn.jsdelivr.net/npm/tocbot@4.12.0/dist/tocbot.min.js" ></script>



  <script  src="https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.js" ></script>



  <script  src="https://cdn.jsdelivr.net/npm/anchor-js@4.3.0/anchor.min.js" ></script>



  <script defer src="https://cdn.jsdelivr.net/npm/clipboard@2.0.6/dist/clipboard.min.js" ></script>



  <script defer src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js" ></script>




  <script  src="https://cdn.jsdelivr.net/npm/typed.js@2.0.11/lib/typed.min.js" ></script>
  <script>
    (function (window, document) {
      var typing = Fluid.plugins.typing;
      var title = document.getElementById('subtitle').title;
      
      typing(title)
      
    })(window, document);
  </script>



  <script  src="/js/local-search.js" ></script>
  <script>
    (function () {
      var path = "/local-search.xml";
      $('#local-search-input').on('click', function() {
        searchFunc(path, 'local-search-input', 'local-search-result');
      });
      $('#modalSearch').on('shown.bs.modal', function() {
        $('#local-search-input').focus();
      });
    })()
  </script>















<!-- 主题的启动项 保持在最底部 -->
<script  src="/js/boot.js" ></script>



<script src="/live2dw/lib/L2Dwidget.min.js?094cbace49a39548bed64abff5988b05"></script><script>L2Dwidget.init({"pluginRootPath":"live2dw/","pluginJsPath":"lib/","pluginModelPath":"assets/","tagMode":false,"debug":false,"model":{"scale":1,"hHeadPos":0.5,"vHeadPos":0.618,"jsonPath":"/live2dw/assets/shizuku.model.json"},"display":{"superSample":2,"width":150,"height":300,"position":"right","hOffset":0,"vOffset":-20},"mobile":{"show":true,"scale":0.5},"react":{"opacityDefault":0.7,"opacityOnHover":0.8},"log":false});</script></body>
</html>
